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;
}