动态规划——POJ 2479 Maximum sum
我觉得这个题目跟2593是一样的题目，就是数据量有些不同。这个题目数据量是50000，但时间只有1000ms，而2593数据量有100000，但时间有3000ms，所以相对而言，这个题目对算法的要求还要高一些，也难怪好多人都在后面发贴说过了2593但这个却没过得了。
考查点：动态规划
思路：在输入的同时，进行一次DP，计算出从左到右的最大值，并把它保存在数组dp的对应的下标元素中，这样之后，对于下标为i的元素，它其中保存的便是前面所 有元素可能的最大连续和。再从右到左进行一次DP，计算从右到左的最大连续和。假设此时已经算到下标为i的元素，那么将sum+dp[i-1]与ans进 行比较，将ans取较大者。最后当i到2的时候ans中的值即为所求的最大值。
提交情况： 记不清是多少Wrong Answer，但肯定是有一次Time Limit Error，因为我有用O(N^2)的DP做过，而且可以通过我想到的所有测试数据。
收获：对动态规划问题如何更好地减少时间有了一点点理解，也复习了一下基本的技能。
经验：做题之前做好充分地分析，包括时间效率、空间效率以及实现地难度。
TLE Code(O(N^2)):（自己想了好久才想出来的，给自己鼓励一下）
#include
using namespace std;
int array[50001], num[50001];
const int MIN = -999999999;
int main()
{
int tcase, n;
cin>>tcase;
int tmp, ans, i, sum;
while(tcase--){
scanf("%d", &n);
tmp = MIN; sum = 0;
for(i = 1; i <= n; i++){
scanf("%d", &num[i]);
sum += num[i];
if(sum > tmp)
tmp = sum;
array[i] = tmp;
if(sum < 0)
sum = 0;
}
tmp = ans = MIN;
sum = 0;
for(i = n; i > 1; i--){
sum += num[i];
if(sum > tmp)
tmp = sum;
if(ans < (array[i-1]+tmp))
ans = array[i-1]+tmp;
if(sum < 0)
sum = 0;
}
cout<
return 0;
}
POJ 2593 Max Sequence
考察点：动态规划
思路：虽然题目给出了3000ms的时间，但考虑到数据量可以达到100000，如果用O(N^2)的算法的话，还是极有可能会超时的，于是决定采用这种O(N)时间效率的动规。在输入的同时，进行一次DP，计算出从左到右的最大值，并把它保存在数组dp的对应的下标元素中，这样之后，对于下标为i 的元素，它其中保存的便是前面所有元素可能的最大连续和。再从右到左进行一次DP，计算从右到左的最大连续和。假设此时已经算到下标为i的元素
，那么将 sum+dp[i-1]与ans进行比较，将ans取较大者。
收获：对这种比较明显的DP问题有了弄深的理解，同时也对时间效率这个概念有了点印象。
#include
using namespace std;
int data[100000],dp[100000];
int main()
{
int n;
int i;
while(cin>>n){
if(!n)
break;
int sum = 0, tmp = -999999999;
for(i = 0; i < n; i++){
scanf("%d", &data[i]);
sum += data[i];
if(sum > tmp)
tmp = sum;
dp[i] = tmp;
if(sum < 0)
sum = 0;
}
sum = 0;
int ans = -999999999;
for(i = n-1; i > 0; i--){
sum += data[i];
if(dp[i-1]+sum > ans)
ans = dp[i-1]+sum;
if(sum < 0)
sum = 0;
}
cout<
return 0;
}
POJ.1015
题意概要：在很遥远的地方，有一个很古怪法庭，里面有n(0
输入：
对于每一组数据。
第一行：n m
以下n行：d1 p1...di pi..dn pn
文件以n=0 m=0作为结束。
输出：
第一行：Jury #t。。t为第几组输出
第二行：Best jury has value ans_d for prosecution and value ans_p for defence: ans_d,ans_p是最优的d值之和与p值之和。
第三行：jury1 jury2...jury.m 代表所选的培训团。每个整数前加一个空格。
算法：
首先，是建立状态方程。如果我们要在n个人中选m个出来。对于第n个陪审员，我们可以选他，也可以不选他。如果，我们选他的话，那么。对应的子问题就是在剩下的n-1个人中选m－1个。如果，我们抛弃他的话。那么，对应的n-1的个中选m个人。此外，还有在做选择前已经累加的d值，和p值，对最优解的选择也是有影响的。如果。已经累加的d值大于p值，那么，所谓的最优解当然是选p略大于d的拉。很容易想到，我们已经累加的d,与p值最其子问题的影响，是他们的差值。
所以，我们可以推算出以下状态方程。
DP[m,n,step]=Best(DP[m-1,n-1,step+dn-pn],DP[m,n-1,step])
step=sum(d)-sum(p).
Best(a,b)=(|a.d-a.p|<|b.d-b.q|)or((|a.d-a.p|==|b.d-b.q|)&&(a.d+a.p>b.d+b.q))?a:b.
然后是，对于陪审团组合的选择可。本人用一个数组choose[m,n,step]来记录DP[m,n,step]取最优值时是选择了n..(choose=1)..还是抛弃了他 choose＝0.至于具体怎么通过这个数组来找到这个组合。我并不打算在这里详谈。希望大家自己想一下，或是通过的代码看出来。
#include
#include
int Sum_d[25],Sum_p[25],jury_d[205],jury_p[205];
int Best_d[25][205][805]
,Best_p[25][205][805];
char flag[25][205][805],choose[25][205][805];
int ans_jury[205];
int abs(int num)//返回num的绝对值
{
if(num<0)
return -num;
else
return num;
}
int DP(int n,int m,int& dp_d,int& dp_p)
{
int yes_d,yes_p,no_d,no_p,tm_d=dp_d,tm_p=dp_p;
int tm1,tm2;
if(m==0)
{
return 0;
}//已经选够人
if(m==n)
{
dp_d+=Sum_d[m];
dp_p+=Sum_p[m];
return 0;
}//在a个人里选a个。。
if(flag[m][n][400+tm_d-tm_p])
{
dp_d+=Best_d[m][n][400+tm_d-tm_p];
dp_p+=Best_p[m][n][400+tm_d-tm_p];
return 0;
}//已经算过的状态。
flag[m][n][400+dp_d-dp_p]=1;
no_d=dp_d;
no_p=dp_p;
DP(n-1,m,no_d,no_p);//选择n
yes_d=dp_d+jury_d[n];
yes_p=dp_p+jury_p[n];
DP(n-1,m-1,yes_d,yes_p);//抛弃n
tm1=abs(yes_d-yes_p)-abs(no_d-no_p);
tm2=(yes_d+yes_p)-(no_d+no_p);
if((tm1<0)||((tm1==0)&&(tm2>0)))
{
dp_d=yes_d;
dp_p=yes_p;
choose[m][n][400+tm_d-tm_p]=1;
}
else
{
dp_d=no_d;
dp_p=no_p;
choose[m][n][400+tm_d-tm_p]=0;
}//取最优解
Best_d[m][n][400+tm_d-tm_p]=dp_d-tm_d;
Best_p[m][n][400+tm_d-tm_p]=dp_p-tm_p;//记录状态
return 0;
}
int doSearch(int m,int n,int pos)//搜索培训团组合。
{
int i;
if(m==0)
return 0;
if(m==n)
{
for(i=1;i<=n;i++)
ans_jury[i]++;
return 0;
}
if(choose[m][n][400+pos]==1)
{
ans_jury[n]++;
doSearch(m-1,n-1,pos+jury_d[n]-jury_p[n]);
}
else
{
doSearch(m,n-1,pos);
}
return 0;
}
int main()
{
int i,m,n,t=0;
int ans_d=0,ans_p=0;
while(scanf("%d%d",&n,&m),m+n>0)
{
t++;
Sum_d[0]=0;
Sum_p[0]=0;
ans_d=0;
ans_p=0;
memset(flag,0,sizeof(flag));
memset(choose,0,sizeof(choose));
memset(ans_jury,0,sizeof(ans_jury));
for(i=1;i<=n;i++)
{
scanf("%d%d",&jury_d[i],&jury_p[i]);
if(i<=m)
{
Sum_d[i]=Sum_d[i-1]+jury_d[i];
Sum_p[i]=Sum_p[i-1]+jury_p[i];
}
}
DP(n,m,ans_d,ans_p);
doSearch(m,n,0);
printf("Jury #%d\nBest jury has value %d for prosecution and value %d for defence:\n",t
,ans_d,ans_p);
for(i=1;i<=n;i++)
{
if(ans_jury[i])
printf(" %d",i);
}
printf("\n\n");
}
return 0;
}
poj 1042 : Gone Fishing (贪心)
为了叙述方便,把钓5分钟鱼称为钓一次鱼,假设从湖泊1走到湖泊x,则路上花去时间T=(t[1]+t[2]+……+t[x-1]),在这个前提下,可以知道对于给出的总时间h总共能钓多少次鱼,即钓鱼次数num=12*h-T,现在,采取贪心策略,每次选一个鱼最多的湖泊钓一次鱼,对于每个湖泊来说,由于任何时候鱼的数目只和在该湖里钓鱼的次数有关,和钓鱼总次数无关,所以该策略是最优的.由于从池塘1出发,每次选择鱼最多的池塘钓鱼,在该池塘钓过后就减去公差,然后再去最大值的池塘钓鱼(在某一池塘处若该池塘鱼的数目有k次这n个池塘中鱼的数目的最大数目(包括每次减去公差后的数目),那么就相应的将总共的鱼的数目加上在池塘这次能钓到的鱼的数目和将对应的时间加上k*5分钟(即k次为最大值,就在该池塘处钓k次鱼后在到右边的池塘钓鱼,并不是每一次选取鱼的数目最大的池塘钓一次鱼后，再换地方选取最大地方的池塘钓鱼),用方程表到就是MAX{max{1——k}}(1<=k<=n),表达的含义是:依次求出前k个池塘(编号为:1——k)的最大值,然后在求出在这些最大值中的最大值.
#include
#include
#include
using namespace std;
int f[28];
int d[28];
int t[28];
int b[28];
int bb[28];
int ff[28];
int sum;
int main()
{
int i,j,h,n,max,pos,num,total;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
break;
scanf("%d",&h);
h*=12; //总的时间
for(i=1;i<=n;i++)
scanf("%d",&f[i]); //各池塘鱼的数目
for(i=1;i<=n;i++)
scanf("%d",&d[i]); //各池塘鱼递减的公差
for(i=1;i<=n-1;i++)
scanf("%d",&t[i]); //从池塘i——i+1所用的时间
max=-1; //表示最大值
for(i=1;i<=n;i++) //依次求出1——i池塘能钓到鱼的数目的最大值
{
sum=0;
num=h;
memset(b,0,sizeof(b)); //标记各池塘钓鱼的次数
for(j=1;j
num-=t[j];
ff[j]=f[j];
}
ff[i]=f[i];
for(num;num>0;num--)
{
pos=1; //标记最大值的下标
for(j=2;j<=i;j++) //求最大值
if(ff[j]>ff[pos])
pos=j;
if(ff[pos]>0)
sum+=ff[p
os];
b[pos]++;
if(ff[pos]>0)
{
ff[pos]-=d[pos];
if(ff[pos]<0)
ff[pos]=0;
}
}
if(max
max=sum;
for(j=1;j<=n;j++)
bb[j]=b[j];
}
}
printf("%d",5*bb[1]);
for(i=2;i<=n;i++)
printf(", %d",5*bb[i]);
printf("\nNumber of fish expected: %d\n\n",max);
}
return 0;
}
POJ 1141 Brackets Sequence 动态规划
设dp[i,j]为从位置i到位置j需要加入字符的最小次数，有dp[i,j]=min(dp[i,k]+dp[k+1,j])，其中i<=k
#include
using namespace std;
const int MAXN = 110;
char str[MAXN];
int dp[MAXN][MAXN],path[MAXN][MAXN];
void output(int i,int j){
if(i>j) return;
if(i==j){
if(str[i]=='[' || str[i]==']') printf("[]");
else printf("()");
}
else if(path[i][j]==-1){
printf("%c",str[i]);
output(i+1,j-1);
printf("%c",str[j]);
}
else{
output(i,path[i][j]);
output(path[i][j]+1,j);
}
}
int main(){
int i,j,k,r,n;
while(gets(str)){
n=strlen(str);
if(n==0){
printf("\n");
continue;
}
memset(dp,0,sizeof(dp));
for(i=0;i
dp[i][j]=INT_MAX;
if((str[i]=='(' && str[j]==')')||(str[i]=='[' && str[j]==']'))
if(dp[i][j]>dp[i+1][j-1])
dp[i][j]=dp[i+1][j-1],path[i][j]=-1;
for(k=i;k
dp[i][j]=dp[i][k]+dp[k+1][j],path[i][j]=k;
}
output(0,n-1);
printf("\n");
}
return 0;
}
POJ1050 To the Max
这个题目很经典的说，O（N^3）的DP。
首先偶们考察这样的题目，简化版：
已知一列数，求任意连续若干个数和的最大值。
SAMPLE： 3 2 -6 2 -1 7
原数3 2 -6 2 -1 7
处理3 5 -1 2 1 8
因为是连续若干个自然数的和，那么，前面的某个数字取与不取的条件在于：以前面这个数字为结尾的连续数的和最大值是否大于0，如果大于0，那么这个数字必然要会出现在包括数字的序列中，否则无法做到最大。
所以，显然。处理的原则是maxn[i]=max{0,maxn[i-1]}+a[i];
由于无须记录位置。所以，可以直
接用一个变量sum代替maxn数组。O(n)的扫描即可。
单列数字的问题解决了，下面我们考察多列数字的
sample:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
我们可以将多列数字转换成单列数字来做！ 可以这样设想，结果是一个长方形，我们把他压扁，使得宽为1。
引入辅助数组st,st[i][j]代表第i列从第1行开始的数字累加到第j行的值。那么，我们每次压扁的时候，就可以用st[i][j]-st[i][k -1]来表示第i列从第k个数字累加到第j个数字的值。达到压缩的效果。然后用上面单列数字的方法来做。
算法时间复杂度O (N^3)
#include
using namespace std;
int Rectangle[100][100];
int DpRectangle[100];
int Single_Rectangle[100];
int Max = 0;
int main()
{
int N,i,j,k;
//输入矩形数组
cin>>N;
for( i = 0; i < N ; ++i){
for( j = 0;j < N; ++j )
{
cin>>Rectangle[i][j];
}
}
//动态规划过程N^3的时间复杂度
for( i = 0; i < N; ++i)
for( j = 0; j < N; ++j)
{
//初始化一维记录数组为零
for( k = 0; k < N; ++k )
Single_Rectangle[k] = 0;
//把i到j行的数组压缩为一维记录数组
for( k = 0; k < N; ++k ){
for(int z = i; z <= j; ++z)
Single_Rectangle[k] += Rectangle[z][k];
}
//初始化动态数组为零
for( k = 0; k < N; ++k )
DpRectangle[k] = 0;
//动态规划计算Single_Rectangle上的任意连续数的最大值
for( k = 0; k < N; ++k)
{
if( k == 0 )
{
DpRectangle[k] = Single_Rectangle[k];
}
else
{
DpRectangle[k] = ( DpRectangle[k-1] > 0 ? DpRectangle[k-1]: 0 ) + Single_Rectangle[k];
}
Max = Max > DpRectangle[k] ? Max : DpRectangle[k];
}
}
cout<
return 0;
}
POJ 1080 Human Gene Functions(动态规划)
解题思路：
和《算法导论》中动态规划章节的LCS(Longest common subsequence 最长公共子序列)所用例子基本是一样的，都是测两串基因的相似程度，不同之处在于《导论》用LCS表示两基因的相似程度，LCS越长，相似度越大。本题中用下面的核苷相近程度取值表表示两基因相似程度，各相应核苷对匹配值之和越高，相似程度自然越大。
首先回想LCS的解法,
设两基因串为an,bm.a[i],b[j]分别表示a串的第
i个核苷.b串的第j个核苷.ax,by为an,bm的子串;
c[x][y]表示子串ax,by间最长子序列的长度,则c[n][m]表示串an,bm间最长子序列的长度.则有如下的状态转移方程：
c[i][j]=c[i-1][j-1]+1 if i,j>0 a[i]=b[j]
c[i][j]=max(c[i][j-1],c[i-1][j]) if i,j>0 a[i]≠[j]
再思考该动规方程的边界条件:
for i=0 to n do c[i, 0] ← 0 for j=0 to n do c[0, j] ← 0
即每个子序列与长度为0的串的最长子序列的长度为0
此即为LCS的解法
针对本题，对LCS的状态方程稍作修改，
设两基因串为an,bm,a[i],b[j]分别表示a串的第i个核苷,b串的第j个核苷,ax,by为an,bm的子串;
c[x][y]表示子串ax,by间最大相似程度值,则c[n][m]表示串an,bm间最大相似程度值
value(x,y)表示核苷x核苷y的相似程度值,'-'表示核苷为空
则有如下的状态转移方程：
c[i][j]=max(c[i-1][j-1]+value(a[i],b[j]),c[i][j-1]+value('-',b[j]),c[i-1][j]+value(a[i],'-'))
if i,j>0 a[i]≠[j]
再思考该动规方程的边界条件:
for i=0 to n do c[i][0] ← 0 for j=0 to n do c[0][j] ← 0
即每个子序列与空串之间的相似程度值的和为0,至此本题的思路已经清晰
#include
using namespace std;
long a[110],b[110],v[110][110];
long r[][5]={0,-3,-4,-2,-1,-3,5,-1,-2,-1,-4,-1,5,-3,-2,-2,-2,-3,5,-2,-1,-1,-2,-2,5};
long change(char c)
{
switch (c)
{
case'A': return 1;
case'C': return 2;
case'G': return 3;
case'T': return 4;
}
}
int main()
{
long caseNum,aLen,bLen,i,j,tmp,all,aOnly,bOnly;
char c;
cin>>caseNum;
while(caseNum--)
{
cin>>aLen;
for(i=1;i<=aLen;i++)
{
cin>>c;
a[i]=change(c);
}
cin>>bLen;
for(i=1;i<=bLen;i++)
{
cin>>c;
b[i]=change(c);
}
v[0][0]=0;
for(i=1;i<=aLen;i++) v[i][0]=r[a[i]][0]+v[i-1][0];
for(i=1;i<=bLen;i++) v[0][i]=r[0][b[i]]+v[0][i-1];
//临界情况是当前这个点和 "-" 得到的值，
//与前面累加得到的，而不仅仅是当前点得到的值
for(i=1;i<=aLen;i++)
for(j=1;j<=bLen;j++)
{
all=v[i-1][j-1]+r[a[i]][b[j]];
aOnly=v[i-1][j]+r[a[i]][0];
bOnly=v[i][j-1]+r[0][b[j]];
tmp=aOnly>bOnly?aOnly:bOnly;
v[i][j]=all>tmp?all:tmp;
}
cout<
return 0;
}
poj 1221 UNIMODAL PALINDROMIC DECOMPOSITIONS 动态规划
算法分析
动态规划题目的特点就是比较灵活，着手点就比较灵活，分析问题的角度也比较灵活。对于这道题目最直接的方法就是推下前几个数据找规律（其实题目已经帮我们推了前几个数据了）。
这道题目的难点是不知道如何设计状态，我们设计状态的原则是用一个模型去刻画题目中给定的具有特征的事物。对于这道题目，题目要求我们统计一个已知序列总和的单峰序列的个数，那么怎样描述一个单峰序列呢？
由于单峰序列是对称的，其实我们只要一对折就变成一个降序（或升序）了。对于一个降序我们可以用它的总和和它最小的数来刻画它。最后我们关心的是所有总和为n的最小为i的序列的总个数。
于是我们设计状态opt[i][j]表示总和为i，最小的数为j的序列的个数。有了这个状态，我们就来思考下决策。对于一个已知了总和i和最小的数是j的序列，构成他们的序列可能有多少呢，其实就是总和为i–2 *j，最小的数位k(j<＝k<=i-2*j)。于是得到状态转移方程：
opt[i][j] = ∑opt[i-2*j][k](j<=k<=i – 2 * j)
时间复杂度 = 状态数 × 决策数 ＝ O(n2) * n = O(n3)
空间复杂度 = 状态数 = O(n2)
注意：
结果可能超过long 用int64
可能会有人问为什么状态中的j用来表示最小而不是最大呢？其实很简单如果用j表示最大的数，那么在做决策的时候将要考虑最大的数在中间还是两边?也就是说最大的数是否是唯一的。不能够确定，而表示最小的数，那么最小的数只有边界的时候opt[i][i]是一个，其余情况都是在两边有两个。这样就可以方便我们做决策了。
#include "stdio.h"
#define MAXN 250
__int64 opt[MAXN][MAXN];
int n;
__int64 ans;
int main()
{
int i,j,k;
for (i = 0; i
opt[1][1] = 1;
opt[2][1] = 1;
opt[2][2] = 1;
for (i = 3; i
{
if (i - 2 * j == 0)
opt[i][j]++;
else
for (k = j; k<=i - 2 * j; k++)
opt[i][j] += opt[i - 2 * j][k];
}
while (scanf("%d",&n) != EOF && n)
{
ans = 0;
for (i = 0; i<=n / 2; i++)
ans += opt[n][i];
printf("%d %I64d\n",n,ans);
}
return 0;
}
POJ 1260 Pearls 【动态规划】
【题目大意】
要买若干种价值的珍珠，但买某种珍珠必须多付10颗此种珍珠的价钱，及如果买
价值为1的珍珠100颗，必须付的钱数为110。一颗珍珠可以用比它贵的珍珠充数，因此买多种珍珠的时候用贵的代替便宜的可能更省钱。例如买100颗价值为2的、1颗价值为1的，此时买101颗价值为2的为较优方案。输入要买的若干种珍珠，可用高价珍珠充数的条件下，问最少需要花费多少钱。
【解题思路】
可以将问题分解为最优子问题，假设有价值为m到n的珍珠，则珍珠最大价值为k(m
【源程序】
#include
using namespace std;
long a[1100],p[1100],sum[1100],ans[1100];
int main()
{
long t,n,i,j;
cin>>t;
while(t--)
{
cin>>n;
memset(sum,0,sizeof(sum));
for(i=1;i<=n;i++)
{
cin>>a[i]>>p[i];
sum[i]=sum[i-1]+a[i];
//sum数组用来记录累加和，方便以后取某段价值珍珠的和
}
for(i=1;i<=n;i++)
{
ans[i]=(sum[i]+10)*p[i];//只用最后一种价值买该价值要求买的珍珠数
for(j=1;j
}
cout<
return 0;
}
POJ 2411 Mondriaan's Dream
解题思路：
首先还是状态的表示，用0表示没有放木块，用1表示放了木块。此外，对于一个横放的木块，对应的两位都用1表示；对于一个竖放的木块，第一行用1表示，第二行用0表示。这只是一种设状态的方式，当然还有别的设法，但是这种方法在接下来就会发现优点。
状态表示完就要处理转移了，如何判断一个转移是否合法比较难办，用一个dfs却可以简洁的解决这个问题。
对于上一行到下一行的转移，规定上一行一定填满，这样有三种方式：
dfs(col + 1, (s1 << 1) | 1, s2 << 1, n);
dfs(col + 1, s1 << 1, (s2 << 1) | 1, n);
dfs(col + 2, (s1 << 2) | 3, (s2 << 2) | 3, n);
第一种上面是1，那么下面一定是0，表示是一个竖放的木块。
第二种上面是0，就是说这个位置一定是一个竖放木块的下半截，那么下一行肯定是要另起一行了，放一个竖放或者横放的木块都必须是1。
第三种相当于上下两行各放一个横木块。
实现的时候我用了一个vector记录每个状态所有可行的转移，这样在dp的时候可以加快一些效率。
还有一个问题需要考虑，那就是初值和最终的结果。如果寻找
合法状态，依然比较麻烦，假设共有n行，可以分别在这n行上下新加两行。下面一行都是1，由于第n行肯定要填满，这样新加的全1的行就相当于顶住了第n行使其没有凸出（有凸出那么第n+1行有0），而通过第n行到第n+1行转移保留了所有合法状态；同理最上面加的那行保证第一行没有凸出。最后第n+1行对应全1的状态就是最终的结果了。通过新加行巧妙地解决了初值和终值。
实现的时候也需要注意一下，在TSP问题中，外层循环是状态，内层是点，之所以这样写因为在枚举点的时候，可能会从比当前编号大的点转移，但是由于无论怎样转移过来的状态肯定比当前状态小（去掉了1），所以先从小到大枚举状态就保证转移过来的状态一定是算过的。而这个题目里面正好反过来，因为状态可能从比当前状态大的状态转移过来，而行数肯定是从编号小的行转移，因此先枚举行就能保证转移过来的状态一定是更新过的。
#include
#include
#include
using namespace std;
const int N = 11;
vector
void dfs(int col, int s1, int s2, int n)
{
if (col >= n)
{
if (s1 < (1 << n) && s2 < (1 << n))
g[s2].push_back(s1);
return;
}
dfs(col + 1, (s1 << 1) | 1, s2 << 1, n);
dfs(col + 1, s1 << 1, (s2 << 1) | 1, n);
dfs(col + 2, (s1 << 2) | 3, (s2 << 2) | 3, n);
}
long long calc(int m, int n)
{
if (m < n) swap(m, n);
dfs(0, 0, 0, n);
int state = 1 << n;
dp[0][0] = 1;
for (int i = 1; i <= m + 1; i++)
for (int s = 0; s < state; s++)
for (int j = 0; j < g[s].size(); j++)
dp[i][s] += dp[i-1][g[s][j]];
return dp[m+1][state-1];
}
int main()
{
int m, n;
while (scanf("%d %d", &m, &n) == 2)
{
if (m == 0 && n == 0)
break;
for (int i = 0; i < (1 << N); i++)
g[i].clear();
memset(dp, 0, sizeof(dp));
printf("%I64d\n", calc(m, n));
}
return 0;
}
POJ1276 Cash Machine DP（GCC语言）
读过题目以后就会发现这是一道多重背包问题，如果你没发现那建议你看我之前写过的东西，先了解下动态规划的入门知识。
何谓多重背包，就是在原来经典的0/1背包的基础上规定一个物品可以背有限次，也是区别于无限背包的特点之一。其实解决的方法很简单，只要把一个物品的多次看做是另一个物品，也就是说产生一种新的物品这个物品的重量是原来的两倍，三倍，…n倍。这样就将多重背包转化成了典型的0/1背包了。
#include
#include
#define MAXN 100
#define MAXM 100010
int opt[MAXM];
int v[MAXN];
int n,m;
int main()
{
int i,count,k,a,d;
while (scanf("%
d",&m) != EOF)
{
scanf("%d",&n);
count = 0;
for (i = 1; i<=n; i++)
{
scanf("%d %d", &a,&d);
k = 1;
while (a - k >=0)
{
a = a - k;
count++;
v[count] = d * k;
k = k * 2;
}
if (a)
{
count++;
v[count] = d * a;
}
}
for (i = 1; i<=m; i++)
opt[i] = 0;
opt[0] = 1;
for (i = 1; i<=count; i++)
for (k = m; k>=v[i]; k--)
opt[k] = opt[k] | opt[k - v[i]];
i = m;
while (opt[i] == 0) i--;
printf("%d\n",i);
}
return 0;
}