即将 AFO 的老年选手

题解 P7240 【[JSOI2014] 打兔子】

2021-01-13 22:19:28


广告


首先特判 $k\geq\left\lceil\frac{n}{2}\right\rceil$ 的情况,此时可以消灭所有兔子。

但是上面的特判有一个例外:当 $n=3,k=2$ 时只能消灭两块菜地中的兔子,显然打最多的两块。

考虑剩下的情况。容易发现,最优解中不会存在相邻的两块菜地都开过枪。

考虑一个 DP:设 $dp_{i,j,0/1}$ 表示前 $i$ 块菜地,开了 $j$ 枪,当前菜地开没开枪,最多能消灭多少只兔子。

转移有以下几种:

  • 下一块不开枪:$dp_{i,j,0}\to dp_{i+1,j,0}$,$dp_{i,j,1}\to dp_{i+1,j,0}$。
  • 这一块没开枪,下一块开枪:$dp_{i,j,0}+a_{i+1}\to dp_{i+1,j+1,1}$。
  • 这一块开枪,下一块不开枪,再下一块开枪:$dp_{i,j,1}+a_{i+1}+a_{i+2}\to dp_{i+2,j+1,1}$。

然而这个 DP 有一个问题:花园是一个环。于是我们只需要在 $1,n$ 都不开枪、$1$ 开枪、$n$ 开枪三种情况中取个 $\max$ 就好了,可以通过更改边界条件实现。

代码是去年写的。

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

template<typename T>
inline void chkmax(T& x,T y) { if (y>x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=4000+10;

int n,k,a[N];
int dp[N][N][2];

inline void calc() {
    for (re int i=1;i<n;++i)
        for (re int j=0;j<=k;++j) {
            chkmax(dp[i+1][j][0],max(dp[i][j][0],dp[i][j][1]));
            if (j+1<=k) chkmax(dp[i+1][j+1][1],dp[i][j][0]+a[i+1]);
            if (i+2<=n) chkmax(dp[i+2][j+1][1],dp[i][j][1]+a[i+1]+a[i+2]);
        }
}

inline int f() {
    int t=a[n]; a[n-1]+=a[n],a[n]=0;
    memset(dp,0xc0,sizeof(dp)),dp[1][1][1]=a[1]; calc();
    a[n]=t,a[n-1]-=a[n];
    return dp[n][k][0];
}
inline int g() {
    memset(dp,0xc0,sizeof(dp)),dp[1][0][0]=0; calc();
    return max(dp[n][k][0],dp[n][k][1]);
}

int main() {
    n=read(),k=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    if (n==3&&k==2) { sort(a+1,a+n+1); return printf("%d\n",a[2]+a[3]),0; }
    if (k>=(n+1)/2) { int ans=0;
        for (re int i=1;i<=n;++i) ans+=a[i];
        return printf("%d\n",ans),0;
    }
    int ans=max(f(),g()); reverse(a+1,a+n+1); chkmax(ans,f());
    printf("%d\n",ans);
    return 0;
}