一些动规题

也来自义冢OJ

【USACO3.1.2】总分

描述

学生在我们USACO的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能的多得分，这需要你的帮助。

我们可以从几个种类中选取竞赛的题目，这里的一个“种类”是指一个竞赛题目的集合，解决集合中的题目需要相同多的时间并且能得到相同的分数。你的任务是写一个程序来告诉USACO的职员，应该从每一个种类中选取多少题目，使得解决题目的总耗时在竞赛规定的时间里并且总分最大。

输入包括竞赛的时间：M，题目种类数：N和。后面的每一行将包括两个整数来描述一个"种类": 第一个整数说明解决这种题目能得的分数(1 <= points <= 10000)，第二整数说明解决这种题目所需的时间(1 <= minutes <= 10000)。你的程序应该确定我们应该从每个"种类"中选多少道题目使得能在竞赛的时间中得到最大的分数。

来自任意的"种类"的题目数目可能是任何非负数(0或更多)。

輸入

第 1 行: M, N–竞赛的时间和题目"种类"的数目。 　　第 2-N+1 行: 两个整数:每个"种类"题目的分数和耗时。

輸出

单独的一行包括那个在给定的限制里可能得到的最大的分数。

輸入範例 1

300 4
100 60
250 120
120 100
35 20

輸出範例 1

605

提示

1 <= M <= 10,000 1 <= N <= 10,000 种题目的分数在1…10000范围内；解答所需时间在1…10000范围内

思路

完全背包问题，顺着填

i：考虑前i道题

j：总时间

#include<cstdio>
#include<iostream>
using namespace std;

const int MAXN=10000+5;

struct js{
	int tm,mark;
};

int n,m;
js a[MAXN];
int f[MAXN];

int main(){
	cin>>m>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i].mark>>a[i].tm;
	}
	f[0]=0;
	for(int i=1;i<=m;++i){
		for(int j=1;j<=n;++j){
			if(i-a[j].tm>=0){
				if(f[i-a[j].tm]+a[j].mark>f[i]){
					f[i]=f[i-a[j].tm]+a[j].mark;
				}
			}
		}
	}
	cout<<f[m]<<endl;
	return 0;
}

【训练题】该说就说

描述

你已经忍耐太久了。现在是时候把你对大家的看法说出来了。

假设你对n个人说出自己的看法，在和第 i 个人说完后，你的健康指数将减少 g[i]，而你的快乐指数将增加 h[i]。你可以和每一个人最多说一次，并且你不必按照特定顺序进行。

你的目标是得到尽可能多的快乐。假设你最初的健康指数为1000，而快乐指数为0。如果你的健康指数为0或负数，即使你得到再多快乐，你也只会痛苦地死去。

现在编写程序请你计算出你可以得到的最大快乐指数。

輸入

第1行：1个正整数N，表示有N个人。　　第2行：N个整数，第i个整数表示你对第i个人说话会失去的健康指数g[i]。　　第3行，N个整数，第i个整数表示你对第i个人说话会得到的快乐指数h[i]。

輸出

输出共1行，1个整数，表示你可以得到的最大快乐指数。

輸入範例 1

3
10 210 790
200 300 250

輸出範例 1

500

提示

对于30%的数据有：1<=N<=20　　对于100%的数据有：1<=N<=200　　所有数据中都有：0

思路

0/1背包，倒着填

i:第i个人

j:减掉的健康度

#include<cstdio>
#include<cstring>
#include<iostream>
#define max(a,b) (a>b)?(a):(b)
#define fuck(a,b,c) for(int a=b;a<=c;++a)
#define shit(a,b,c) for(int a=b;a>=c;--a)
using namespace std;

const int MAXN=200+5;

int f[1005];
int g[MAXN],h[MAXN];
int n;


int main(){
	cin>>n;
	memset(f,0,sizeof(f));
	fuck(i,1,n){
		cin>>g[i];
	}
	fuck(i,1,n){
		cin>>h[i];
	}
	fuck(i,1,n){
		shit(j,1000,1){
			if(j-g[i]>0){
				f[j]=max(f[j],f[j-g[i]]+h[i]);
			}
		}
	}
	cout<<f[1000]<<endl;
	return 0;
}

PS

这个设定也太奇怪了吧。。。

因为对人说出了自己的看法，然后被打了

然后就会掉血。。。。。。。。。

（代码稍微皮了一下

【训练题】最大约数和

描述

选取和不超过 S 的若干不同正整数，使得所有数的约数（不含它本身）和为最大！

輸入

一个整数 S 。

輸出

输出最大的约数之和。

輸入範例 1

11

輸出範例 1

9

提示

对于30%的数据：S<=10对于100%的数据：S<=1000

思路

感谢Perisino大佬（提供第二种思路

s[i]表示i的约数和

我的思路

原本是这样想的：

f[第几个数][它们的和]=它们的约数和;
f[i][j]=max(f[i-1][j-i]+s[i],f[i-1][j]);

然后发现是错的

然后改修了Perisino大佬的方法

然后发现求约数和的函数写错了。

这里的约数和不包括自身而我开始把自身加进去了

然后发现是对的

真棒~

 #include<cstdio>
#include<queue>
#include<iostream>
using namespace std;

const int MAXN=1005;

deque<int> ys[MAXN];
deque<int> s;

int f[MAXN];
	
int yueshuhe(int x);

int main(){
	int he;
	cin>>he;
	yueshuhe(he);
	for(int i=1;i<=he;++i){
		for(int j=i;j<=he;++j){
			f[j]=max(f[j-i]+s[i],f[j]);
		}
	}
	cout<<f[he]<<endl;
	return 0;
}

int yueshuhe(int x){
	s.resize(x+5);
	for(int i=1;i<=x;++i){
	    for(int j=1;j<=x/i;++j){
	        ys[i*j].push_back(i);
	        s[i*j]+=i;
	    }
    	s[i]-=i;
	}
}

Perisino大佬的思路

f[i]=max(f[i],s[j]+f[i-j]);
外层：和为i
内层：j与已经选中的数相加=i

所以

for(int i=1;i<=he;++i){
    for(int j=1;j<=i;++j){
        f[i]=max(f[i],f[i-j]+s[j]);
    }
}

PS：

? 大佬的原版代码直接在求好的s数组上dp看得我一脸懵逼。。。

【训练题】背包问题[4]

Description

问题1:装满背包

给出 N 个物品，第 i 个物品的体积为 v[i]，价值为 p[i],现在需要选择一些物品装满容量为 C 的背包，所能获得的最大价值，如果不能装满，则输出-1。

问题2:K背包

给出 N 个物品，第i个物品的体积为 v[i]，价值为 p[i],现在需要选择 K 个装入容量为 C 的背包，所能获得的最大价值，如果无解，则输出-1。

Input

第 1 行：两个整数 C 和 N 。

? 接下来的N行：每行两个整数，表示 v[i] 和 p[i] 。

? 最后一行，一个整数 K （针对问题2）。

Output

第 1 行：一个整数，表示问题1的解，不能装满，则输出-1。　　第 2 行：一个整数，表示问题2的解，如果无解，则输出-1。

輸入範例

【样例1】
　　10 5
　　2 2
　　8 7
　　3 3
　　5 4
　　7 8
　　3

【样例2】
　　10 5
　　2 2
　　8 7
　　3 3
　　5 4
　　7 8
　　4

【样例3】
　　16 5
　　3 3
　　1 3
　　2 1
　　5 4
　　4 6
　　3

輸出範例

【样例1】
　　11
　　9

【样例2】
　　11
　　-1

【样例3】
　　-1
　　13

提示

1<=K<=N<=100　　1<=v[i]<=C<=20000　　1<=p[i]<=1,000,000

思路

对于问题一，只要把0以后的项初始化成-inf即可

对于二我很懵逼

然后感谢dyx大佬share了AC代码，让我体验到了这道题的精髓

f[i][j][l]=max(f[i-1][j][l],f[i-1][j-1][l-v[i]]+p[i]);
其中
	i表示物品数目
	j表示已选的物品数量
	l表示背包已占用的容量
	
空间压到二维（0/1背包倒着填）：
for(int i=1;i<=n;++i){
	for(int j=k;j>=1;--j){
		for(int l=c;l>=v[i];--l){
			f2[j][l]=max(f2[j][l],f2[j-1][l-v[i]]+p[i]);
		}
	}
}

完整代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int MAXN=105,MAXC=2e4+5,INF=0x3f3f3f3f;

int v[MAXN],p[MAXN];
int f1[MAXC],f2[MAXN][MAXC];
int n,c,k;

int main(){
	cin>>c>>n;
	for(int i=1;i<=n;++i){
		cin>>v[i]>>p[i];
	}
	cin>>k;
	for(int j=1;j<=c;++j){
		f1[j]=-INF;
	}
	for(int i=1;i<=n;++i){
		for(int j=c;j>=v[i];--j){
			f1[j]=max(f1[j],f1[j-v[i]]+p[i]);
		}
	}
	
	for(int i=1;i<=n;++i){
		for(int j=k;j>=1;--j){
			for(int l=c;l>=v[i];--l){
				f2[j][l]=max(f2[j][l],f2[j-1][l-v[i]]+p[i]);
			}
		}
	}
	cout<<(f1[c]<0?-1:f1[c])<<endl<<(f2[k][c]?f2[k][c]:-1)<<endl;;
	return 0;
}

PS:

我一直以为k是有k个背包来填。其实这才是我怕一直没做出来的原因

为此我还搜到了这样的题解。。。

丢人！