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:
#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; }