codeforces 234F - Fence

本文主要是介绍codeforces 234F - Fence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

感觉是个背包，开始想用dp[i][j]表示红色容量为j的最小值，同时记录这时i的颜色，但这样状态无法转移，可以再加一维dp[i][j][0]表示i为红色，dp[i][j][1]表示i为绿色，枚举j时表示的是前i个恰好用完j容量，绿色容量为tot[i]-j，所以初始化时dp[0][0][0]=dp[0][0][1]=0，其他为无穷大。

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#define inf 10000000
#define pi acos(-1.0)
#define eps 1e-8
#define seed 131
using namespace std;
typedef pair<int,int> pii;
typedef unsigned long long ULL;
typedef long long LL;
const int maxn=100005;
int n;
int h[205];
int a,b;
int dp[205][40005][2];
int tot[205];
//0:红，1：绿
int main()
{freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);tot[0]=0;scanf("%d",&n);scanf("%d%d",&a,&b);for(int i=1;i<=n;i++){scanf("%d",&h[i]);tot[i]=tot[i-1]+h[i];}dp[0][0][0]=dp[0][0][1]=0;int ans=inf;for(int i=1;i<=a;i++)dp[0][i][0]=dp[0][i][1]=inf;for(int i=1;i<=n;i++){for(int j=min(tot[i],a);j>=0;j--){dp[i][j][0]=dp[i][j][1]=inf;if(tot[i]-j<=b){if(tot[i]-j>=h[i])dp[i][j][1]=min(dp[i-1][j][1],dp[i-1][j][0]+min(h[i],h[i-1]));if(j>=h[i])dp[i][j][0]=min(dp[i-1][j-h[i]][0],dp[i-1][j-h[i]][1]+min(h[i],h[i-1]));}if(i==n){ans=min(ans,dp[i][j][0]);ans=min(ans,dp[i][j][1]);}}}if(ans==inf)ans=-1;printf("%d",ans);return 0;
}

这篇关于codeforces 234F - Fence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---