lzy的遊戲【思維分析】【背包】

lzy的遊戲

緻敬那個oier。

這道題拿到手還以為要複制一遍弄環之類地想的很複雜。

其實我們要靜下心來觀察性質。

首先：選的東西的消耗卡數和小于等于n。廢話，要不然選個毛。

這個理論的反面形式：隻要選的小于等于n，那就可以選。

我們感性地發現，如果目前不能用，放到最後去，一陣操作後又可以用了。永遠存在至少一張的卡數被滿足。否則卡數和就大于n了。

是以就是個弱智的01背包。

重點

學到的：在不滾動數組的時候，應該繼承上一層答案，然後更新。因為滾動數組本身隐含有繼承答案的意義。

不滾動的

#include<bits/stdc++.h>
using namespace std;
#define in read()
int in{
	int cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){
		ch=getchar();if(ch=='-')f=-1;
	}
	while(isdigit(ch)){
		cnt=cnt*10+ch-48;
		ch=getchar();
	}return cnt*f;
}
int n;
int value[1003],weigh[1003];
int f[1003][1003];
signed main(){
	n=in;for(int i=1;i<=n;i++){
		value[i]=in;weigh[i]=in;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=max(f[i][j],f[i-1][j]);
			if(j>=weigh[i])
			f[i][j]=max(f[i][j],f[i-1][j-weigh[i]]+value[i]);
		}
	}
	//for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cout<<f[i][j]<<" ";cout<<endl;}
	cout<<f[n][n];
	return 0;
}
           

滾動的

#include<bits/stdc++.h>
using namespace std;
#define in read()
int in{
	int cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){
		ch=getchar();if(ch=='-')f=-1;
	}
	while(isdigit(ch)){
		cnt=cnt*10+ch-48;
		ch=getchar();
	}return cnt*f;
}
int n;
int value[1003],weigh[1003];
int f[1003];
signed main(){
	n=in;for(int i=1;i<=n;i++){
		value[i]=in;weigh[i]=in;
	}
	for(int i=1;i<=n;i++){
		for(int j=n;j>=weigh[i];j--){
			f[j]=max(f[j],f[j-weigh[i]]+value[i]);
		}
	}
	//f//or(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cout<<f[i][j]<<" ";cout<<endl;}
	//int ans=0;
	//for(int i=1;i<=n;i++)ans=max(ans,f[i][n]);cout<<ans;
	cout<<f[n];
	return 0;
}