【BZOJ 5038 不打兔子】

Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 22 Solved: 8
[Submit][Status][Discuss]

Description

勤劳的JYY在花园里面种了好多胡萝卜！可是，今天早上JYY发现一大群从JSOI王国里面跑来的兔子把他的花园全部

占满了！兔子们把胡萝卜吃光了，JYY靠什么过冬呢！忍无可忍的JYY决定取出他的强力猎枪来消灭这些兔子。JYY

的花园是一个由N个块小菜地顺次连接所形成的圆环。菜地由1到N编号。第i号菜地和第i+1号菜地是相邻的。由于

是环形的花园，所以1号菜地和N号菜地也是相邻的。现在，第i号菜地上有Ri只兔子。JYY的猎枪有K发子弹，每次J

YY可以选择一块菜地打一枪，然后这块菜地上的兔子就全部都被消灭了。但是由于JYY的猎枪威力太大，会吓到相

邻菜地上的兔子，所以，如果JYY朝i号菜地打了一枪，那么i+1号菜地上的兔子就会跑到i+2号菜地上去，同样的，

i-1号菜地上的兔子也会跑到i-2号菜地上去。JYY想知道，如何用这K发子弹，消灭尽量多的兔子呢？

Input

输入文件的第一行包含两个整数N和K；

接下来一行N个整数，第i个整数为Ri。

3≤N≤4000，0≤K≤4000，0≤Ri≤10^5。

Output

输出一行一个整数，表示JYY最多可以消灭的兔子个数。

Sample Input

5 2
6 1 5 3 4

Sample Output

13
【样例说明】
首先JYY朝1号菜地打一枪，然后菜地里面的兔子数量就变成了
0 0 6 7 0
接着JYY再朝4号菜地打一枪就可以一共消灭13只兔子了

题解：

①尝试转化问题：先得出结论“间隔地选择开枪位置最优”，那么我们可以将连续间隔的一部分划分为一个区间(例如000000),这里面的生物都会被打死。

②划分区间后，原问题转化为区间DP:f[i][j][1/0]表示在i位置,已经开了j枪,是否向后延伸区间。

③转移建议使用草稿纸画一画:

f[i+1][j][0]=max(f[i+1][j][0],f[i][j][0]) 不开枪,继续向前走形成下一个区间
   f[i+1][j+1][1]=max(f[i+1][j+1][1],f[i][j][0]+a[i+1]) 走的下一步并开一枪,同时归为当前区间
   f[i+1][j][0]=max(f[i+1][j][0],f[i][j][1]) 不开枪,该区间到此为止,走入下一个区间
   f[i+2][j+1][1]=max(f[i+2][j+1][1],f[i][j][1]+a[i+1]+a[i+2]) 当前开了枪,下一步不开枪并归为当前区间,所以再走一步

④处理环：如果1,n不在同一区间便没啥。如果在一个区间,就枚举是选择1开枪还是在n开枪。(代码中体现为sign)

#include<cstdio>

#include<cstring>

#include<algorithm>

#define inf 1000000000

#define go(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

int n,k,f[4005][4005][2],a[4005],b[4005],sum,ans;

int Dynamic_Programming(int sign)

{

    if(k*2>n)return sum;

    go(i,1,n)go(j,0,k)f[i][j][0]=f[i][j][1]=-inf;f[1][1][1]=a[1];if(!sign)f[1][0][0]=0;

    go(i,1,n)go(j,0,k)

        f[i+1][j][0]=max(f[i+1][j][0],f[i][j][0]),

        f[i+1][j+1][1]=max(f[i+1][j+1][1],f[i][j][0]+a[i+1]),

        f[i+1][j][0]=max(f[i+1][j][0],f[i][j][1]),

        f[i+2][j+1][1]=max(f[i+2][j+1][1],f[i][j][1]+a[i+1]+a[i+2]);

    if(sign)return f[n][k][1];

    return max(f[n][k][0],f[n][k][1]);

}

int main()

{

    scanf("%d%d",&n,&k);

    go(i,1,n)scanf("%d",&b[i]),a[i]=b[i],sum+=(a[i]=b[i]);

    if(n==3&&k==2){sort(a+1,a+n+1);printf("%d",a[2]+a[3]);return 0;}

    ans=Dynamic_Programming(0);a[1]=0;n++;k++;

    go(i,1,n)a[i+1]=b[i];ans=max(ans,Dynamic_Programming(1));

    go(i,1,n)a[i+0]=b[i];ans=max(ans,Dynamic_Programming(1));

    printf("%d\n",ans);

}//Paul_Guderian

倦得像一朵被风折断的野花,所以我开始变了, 
变得像一团滚动炽热的花火.————汪峰《花火》

巴特西