234f专题

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<s