一些動規題 - 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 個背包來填。其實這才是我怕一直沒做出來的原因~~

~~為此我還搜到了這樣的題解。。。~~

丟人！