一些动规题 - BuringStraw

一些动规题#

也来自义冢 OJ

【USACO3.1.2】总分#

描述#

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

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

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

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

輸入#

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

輸出#

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

輸入範例 1#

輸出範例 1#

提示#

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#

提示#

　　对于 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#

輸出範例 1#

提示#

对于 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背包

　　给出 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】
　　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 个背包来填。其实这才是我怕一直没做出来的原因~~

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

丢人！