题解 P2686 【老虎的题目】

· · 题解

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