【算法】动态规划

【题解】

万物皆动规，每时每刻都要想着DP！特别是这种明显可以序列递推的题目。

一个简单的思路是f[i]表示前i个选择合法方案（第i个可选可不选）的最大效率

f[i]=max(f[i-1],f[j-2]+sum[j~i]),j=i-k+1~i。

然后就可以把f[j]-sum[j+1]加入单调队列了。

单调队列其实很好写的，每次先弹出超限的，然后对于每个i把对应的东西比较队尾后加入队列就可以了。

当然DP优化肯定要先写普通DP来对照和对拍的。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=100010;int n,kind;long long sum[maxn],f[maxn];struct cyc{
    int p;long long x;}q[maxn];int read(){    char c;int s=0,t=1;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}int main(){    n=read();kind=read();    for(int i=1;i<=n;i++)sum[i]=read(),sum[i]+=sum[i-1];    f[0]=0;    int head=0,tail=1;q[head]=(cyc){
    0,0};    for(int i=1;i<=n;i++){        f[i]=f[i-1];        if(q[head].p
         
        
       
      

 

另一种思路是反过来，令f[i]表示不选i的最小放弃值。

f[i]=f[j]+a[i],j=i-k~i-1　　也就是说j+1~i-1部分全选。

这思路就有意思多了。