本文为大型题解集

P2066 机器分配
P1759 通天之潜水

P2066 机器分配

这道题的难点在于要输出分配方案。

CODE

#include<bits/stdc++.h> 
using namespace std;
struct st
{
	int s[200];	
}ans[200][200];
int n,m,c[200][200],f[200][200]; 
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&c[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++)
			for(int k=0;k<=m;k++)
				if(j>=k&&f[i][j]<=f[i-1][j-k]+c[i][k])
				{
					f[i][j]=f[i-1][j-k]+c[i][k];
					ans[i][j]=ans[i-1][j-k];
					ans[i][j].s[i]=k;
				}
	printf("%d\n",f[n][m]);
	for(int i=1;i<=n;i++)
		printf("%d %d\n",i,ans[n][m].s[i]);
	return 0;
}

只是多了一个ans[][]结构体数组而已！

思路

ans[][]的转移方式与f[][]相似。

即，若f[i][j]<=f[i-1][j-k]+c[i][k]（懒得表述），则ans[i][j]=ans[i-1][j-k]+k！这样就记录了方案选择。只是为了方便，使用结构体。

时间复杂度： $O(nm^2)$ 。

P1759 通天之潜水

CODE

#include<bits/stdc++.h>
using namespace std;
struct my
{
	int a[200+5],cnt;
}ans[200+5][200+5];
int n,m1,m2,w1[100+5],w2[100+5],c[100+5],f[200+5][200+5];
int main()
{
	scanf("%d%d%d",&m1,&m2,&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",w1+i,w2+i,c+i);//二维费用，状态数组加一维。
	for(int i=1;i<=n;i++)
		for(int j1=m1;j1>=w1[i];j1--)
			for(int j2=m2;j2>=w2[i];j2--)
				if(f[j1][j2]<f[j1-w1[i]][j2-w2[i]]+c[i])
				{
					f[j1][j2]=f[j1-w1[i]][j2-w2[i]]+c[i];
					ans[j1][j2]=ans[j1-w1[i]][j2-w2[i]];
					ans[j1][j2].a[++ans[j1][j2].cnt]=i;
				}
	printf("%d\n",f[m1][m2]);
	for(int i=1;i<=ans[m1][m2].cnt;i++)
		printf("%d ",ans[m1][m2].a[i]);
	return 0;
}