老师说要帮学弟们做的题。
一道很简单的区间dp。设f[i][j][k][0/1]表示一共要杀k个小兵，选择杀i-j的小兵，此时最后一个杀的小兵是i/j时的答案。
用dfs转移，很简单就可以做出来，但是这样会空超，容易发现k这一维是可以省略的。
#include<cstdio> #include<cstring> #include<algorithm> #define N 310 using namespace std; int n,m,i,j,f[N][N][2],x[N],ans; void dfs(int l,int r,int num){ if (f[l][r][0]>f[0][0][0]||f[l][r][1]>f[0][0][0]) return; if (l>r) return; dfs(l+1,r,num);dfs(l,r-1,num); //int sum=max(f[num][l+1][r][0]+m-(num-(r-l))*(x[l+1]-x[l]),f[num][l][r-1][1]+m-(num-(r-l))*(x[r]-x[r-1])); f[l][r][0]=f[l+1][r][0]+m-(num-(r-l))*(x[l+1]-x[l]); f[l][r][1]=f[l][r-1][1]+m-(num-(r-l))*(x[r]-x[r-1]); f[l][r][0]=max(f[l+1][r][1]+m-(num-(r-l))*(x[r]-x[l]),f[l][r][0]); f[l][r][1]=max(f[l][r-1][0]+m-(num-(r-l))*(x[r]-x[l]),f[l][r][1]); return; } int Abs(int x){ if (x<0) return -x; return x; } int main(){ freopen("kill.in","r",stdin); freopen("kill.out","w",stdout); scanf("%d%d",&n,&m); for (i=1;i<=n;i++) scanf("%d",&x[i]); sort(x+1,x+n+1); for (i=1;i<=n;i++){ memset(f,128,sizeof(f)); for (j=1;j<=n;j++) f[j][j][0]=f[j][j][1]=-Abs(x[j])*i+m; dfs(1,n,i); for (j=1;j<=n;j++) if (f[j][j+i-1][0]>ans) ans=f[j][j+i-1][0]; for (j=1;j<=n;j++) if (f[j][j+i-1][1]>ans) ans=f[j][j+i-1][1]; } printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/Mohogany/p/13774224.html