自动搬运

查看原文

来自洛谷，原作者为

	DоsLikе 这个家伙不懒，但也什么都没有留下

搬运于2025-08-24 21:40:27，当前版本为作者最后更新于2020-12-28 20:48:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P2686老虎的题目

题目描述&样例输入/输出:这里

似乎本题其他dalao的题解都是注重“怎么做”，那本蒟蒻就试着写一篇解释“为什么”的题解吧

主要思路：dp加上一点前缀和（似乎不用也行？）

凭着良心说，这题作为一道绿的dp，还是有一点水的。

dp嘛，必然要三步走的：

1. 定义状态：

通常来讲我们可能不会一下子就定义对了状态，

但是这题的题目描述太直白了，相当于把怎样定义状态直接告诉了我们。

因为题目要求的是连续的一段（线性），所以我们可以通过只枚举左右两个端点来确定这个区间的大小（长度）。

于是我们把 $dp[i][j]$ 定义为左端点为 $i$ ,右端点为 $j$ 这个区间的难度最大值。

2.定义状态转移方程

如果是dp，当你找出了状态转移方程之后，你就解决了这个问题的 80%

							--沃兹基硕德

看题面，首先这道题存在条件的限制，这告诉我们这道题极有可能有两个及以上的转移方程。

我们首先考虑最正常的情况

首先我们来对这种情况做一个限制条件。

题目要求：题面长度的总和，不能超过high，也不能低于low。

也就是说，我们要求出我们正在考虑的这段区间内所有题目的长度的总和来和 $low$ 以及 $high$ 作比较。

这就用到我们的前缀和了。提前算好前缀和可以让我们用O(1)的时间复杂度来获取当前区间的长度和，否则就得用O(n)的复杂度来算，估计得T掉（没试，不过差不多）

在长度满足要求的情况下，我们可以推出这种情况的转移方程为

$dp[i][j]=max(dp[i-1][j-1]+brr[j]-[i-1])$

(注意，上式的brr代表着“难度”数组的前缀和)

那么问题来了，如果这个区间不符合题目的要求呢？？

我们可以把整个枚举长度的过程想成“一个单位一个单位的枚举”

这样的话我们在单位时间里，思考的永远是某一个位置的情况，因此可以得出在不符合要求的情况下的状态转移方程式

$dp[i][j]=max(dp[i-1][j],dp[i][j-1])$

3.初始状态定义

本题的初始状态为 $dp[i][j]=0$ （这没啥好说的）

剩下的一点小细节，在注释里会提到

#include <iostream>
#include <cstdio>
#define maxn 1005
#define ll long long//要开long long 不然会WA掉#3 
using namespace std;
ll arr[maxn];//长度 
ll brr[maxn];//难度 
ll dp[maxn][maxn];
ll n,low,high;//变量名称与题目一致 
int main(){
	cin>>n>>low>>high;
	int tmp;
	for(int i=1;i<=n;i++)cin>>tmp,arr[i]=arr[i-1]+tmp;
	for(int i=1;i<=n;i++)cin>>tmp,brr[i]=brr[i-1]+tmp;//输入的同时顺手把前缀和给处理了 
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//这里，首先要假设枚举到的位置不成立 (不过关于为什么这一点要在前，我本人只是明白但不会解释，希望有dalao能解释一下QWQ)
			if((arr[j]-arr[i-1])>=low&&(arr[j]-arr[i-1])<=high)dp[i][j]=max(dp[i][j],dp[i-1][j-1]+brr[j]-brr[i-1]);//如果符合要求的情况 
		}
	}
	cout<<dp[n][n];//输出即可 
	return 0;
}

总结：代码难度是真的不高，但是确实有几个细节不大好想，一不小心又码了那么多字，有问题请轻喷QAQ