琪露诺速冻青蛙----记忆化搜索与动态规划

洛谷P1725
记忆化搜索显然更简单，因为遍历了所有可能（包括无法实现的解），用时长，最后两个点会TLE

#include<bits/stdc++.h>
using namespace std;

int n,l,r;int v[300005];int f[300005];
int m(int id)
{
    if(id+l>n)return v[id];
    if(f[id])return f[id];
    int max=m(id+l);int t;
    for(int i=l+1;i<=r;i++)
    {
        t=m(id+i);
        if(t>max)max=t;
    }
    f[id]=max+v[id];
    return max+v[id];
}
int main()
{
    cin>>n>>l>>r;
    memset(f,0,sizeof(f));
    for(int i=0;i<=n;i++)
        cin>>v[i];
    cout<<m(0)<<endl;
    return 0;
}

线性动态规划法，从所以的分支中选择有可能实现的分支，有点剪枝的感觉

#include<bits/stdc++.h>
using namespace std;

int n,l,r;int v[200005];int f[200005];
int m()
{
    int i=l;f[0]=v[0];
    while(i<=n+r)
    {
        int begin=i-r>0?i-r:0;
        int max=f[begin];
        //cout<<begin<<" ";
        for(int j=begin;j<=i-l;j++)
            if(f[j]>max)max=f[j];
        if(max!=-10086)
            f[i]=max+v[i];
        //cout<<i<<" "<<f[i]<<endl;
        i++;
    }
    int count=f[n+1];
    for(int i=n+2;i<=n+r;i++)
        if(f[i]>count)count=f[i];
    return count;
}
int main()
{
    cin>>n>>l>>r;int flag=1<<31;
    memset(f,(-10086),sizeof(f));
    //cout<<f[1]<<endl;
    for(int i=0;i<=n;i++)
        cin>>v[i];
    cout<<m()<<endl;
    return 0;
}