DP
dp[i][j][k]前i个栏杆中,有j个被涂成red,当前的栏杆颜色 0 red 1 green
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int INF=(1<<30); int n,a,b,sum; int h[222],dp[2][40040][2]; int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); scanf("%d%d%d",&n,&a,&b); for(int i=1;i<=n;i++) { scanf("%d",h+i); sum+=h[i]; } memset(dp[0],-1,sizeof(dp[0])); dp[0][0][1]=dp[0][0][0]=0; int now=1,pre=0; for(int i=1;i<=n;i++,swap(now,pre)) { memset(dp[now],-1,sizeof(dp[now])); int mi=min(h[i],h[i-1]); for(int j=0;j<=a;j++) { int c=j+h[i]; if(dp[pre][j][0]!=-1) { if(dp[now][c][0]==-1||dp[pre][j][0]<dp[now][c][0]) dp[now][c][0]=dp[pre][j][0]; if(dp[now][j][1]==-1||dp[pre][j][0]+mi<dp[now][j][1]) dp[now][j][1]=dp[pre][j][0]+mi; } if(dp[pre][j][1]!=-1) { if(dp[now][c][0]==-1||dp[pre][j][1]+mi<dp[now][c][0]) dp[now][c][0]=dp[pre][j][1]+mi; if(dp[now][j][1]==-1||dp[pre][j][1]<dp[now][j][1]) dp[now][j][1]=dp[pre][j][1]; } } } int ans=INF; now=pre; for(int i=0;i<=a;i++) { if(sum-i<=b) { if(dp[now][i][0]!=-1) ans=min(ans,dp[now][i][0]); if(dp[now][i][1]!=-1) ans=min(ans,dp[now][i][1]); } } if(ans==INF) ans=-1; printf("%d\n",ans); return 0; }