CodeForces Round #145(234F) - Fence
2186 ワード
喜聞楽見のdp...dp[x][y][z]...前x.にy面積のあるredを表す.そしてx番目はz(0---red,1---green)...前のレイヤx-1については明らかに更新されています.したがって、最初の200のxはスクロール配列に簡略化することができる...
Program:
Program:
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#define ll long long
using namespace std;
int n,a,b,h[205],dp[2][50005][2],sum;
int main()
{
freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
int p,i,k,c,x;
scanf("%d%d%d",&n,&a,&b);
sum=h[0]=0;
for (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;
k=0;
for (p=1;p<=n;p++)
{
k=1-k;
memset(dp[k],-1,sizeof(dp[k]));
for (i=0;i<=a;i++)
{
if (dp[1-k][i][0]!=-1)
{
c=i+h[p]; x=min(h[p-1],h[p]);
if (dp[k][c][0]==-1 || dp[k][c][0]>dp[1-k][i][0])
dp[k][c][0]=dp[1-k][i][0];
if (dp[k][i][1]==-1 || dp[k][i][1]>dp[1-k][i][0]+x)
dp[k][i][1]=dp[1-k][i][0]+x;
}
if (dp[1-k][i][1]!=-1)
{
c=i+h[p]; x=min(h[p-1],h[p]);
if (dp[k][c][0]==-1 || dp[k][c][0]>dp[1-k][i][1]+x)
dp[k][c][0]=dp[1-k][i][1]+x;
if (dp[k][i][1]==-1 || dp[k][i][1]>dp[1-k][i][1])
dp[k][i][1]=dp[1-k][i][1];
}
}
}
int ans=-1;
for (i=0;i<=a;i++)
if (sum-i<=b)
{
if (dp[k][i][0]!=-1 && (ans==-1 || ans>dp[k][i][0]))
ans=dp[k][i][0];
if (dp[k][i][1]!=-1 && (ans==-1 || ans>dp[k][i][1]))
ans=dp[k][i][1];
}
printf("%d
",ans);
return 0;
}