4978:宠物小精灵之收服
题目
三维代码，4分wa，看个思路再接着滚动数组

1、// sort(a+1,a+n+1);不用排序，递推过程中就在不断比较哪种取法能收复最多精灵
2、体力值可以对m取等号

using namespace std;
struct node{int ball;int energy;bool operator<(const node n)const{if(ball==n.ball)return energy<n.energy;return ball<n.ball;}
}a[105];

#include <bits/stdc++.h>
using namespace std;
struct node{int ball;int energy;bool operator<(const node n)const{if(ball==n.ball)return energy<n.energy;return ball<n.ball;}
}a[105];
int dp[105][505][1005];
//dp[i][j][h]前对于i个精灵 允许消耗j体力 h个精灵球能收服的精灵数 
//求dp[k][m-1][n];要给皮卡丘留一个体力  好叭用不着 
int main(){ios::sync_with_stdio(false);cin.tie(0);int n,m,k;//精灵球数量，皮卡丘体力，精灵数量 cin>>n>>m>>k;for(int i=1;i<=k;i++){cin>>a[i].ball>>a[i].energy;}
//	 sort(a+1,a+n+1);for(int i=1;i<=k;i++){for(int j=m;j>=1;j--){for(int h=n;h>=1;h--){if((j>=a[i].energy)&&(h>=a[i].ball)){
dp[i][j][h]=max(dp[i-1][j-a[i].energy][h-a[i].ball]+1,dp[i-1][j][h]);}else dp[i][j][h]=dp[i-1][j][h];}}} cout<<dp[k][m][n]<<" ";int minn=0x3f3f3f;
//		for(int i=1;i<=k;i++){
//		for(int j=1;j<=m;j++){
//			for(int h=1;h<=n;h++){
//				if(dp[i][j][h]==dp[k][m][n])minn=(min(minn,j));
//			}
//		}
//	}int i;for(i=1;i<=m;i++){if(dp[k][i][n]==dp[k][m][n])break;} minn=i;cout<<m-minn;
//	dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]);	return 0;
} 

二维代码

#include <bits/stdc++.h>
using namespace std;
struct node{int ball;int energy;bool operator<(const node n)const{if(ball==n.ball)return energy<n.energy;return ball<n.ball;}
}a[105];
int dp[505][1005]; 
int main(){ios::sync_with_stdio(false);cin.tie(0);int n,m,k;//精灵球数量，皮卡丘体力，精灵数量 cin>>n>>m>>k;for(int i=1;i<=k;i++){cin>>a[i].ball>>a[i].energy;}
//	 sort(a+1,a+n+1);for(int i=1;i<=k;i++){for(int j=m;j>=a[i].energy;j--){for(int h=n;h>=a[i].ball;h--){
//			if(j>=a[i].energy&&h>=a[i].ball){
dp[j][h]=max(dp[j-a[i].energy][h-a[i].ball]+1,dp[j][h]);//	}
//	else dp[j][h]=dp[j][h];}}} cout<<dp[m][n]<<" ";int minn=0x3f3f3f;for(int h=0;h<=n;h++){for(int j=0;j<=m;j++){if(dp[j][h]==dp[m][n])minn=(min(minn,j));}}
//	int i;至多要n个精灵球，至多要m个体力，要达到收服同样精灵的效果
//可能不需要m体力，可能会剩1 2 3…个？从小往大假设，第一次达到同样效果
//的就是实际消耗的体力，剩下的不能再支持收复下一个了，而精灵球给予充分保证 
//	for(i=1;i<=m;i++){
//		if(dp[i][n]==dp[m][n])break;
//	}
//	minn=i;cout<<m-minn;
//	dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]);	return 0;
} 

int i;至多要n个精灵球，至多要m个体力，要达到收服同样精灵的效果可能不需要m体力，可能会剩1 2 3…个？从小往大假设，第一次达到同样效果的就是实际消耗的体力，剩下的不能再支持收复下一个了，而精灵球给予充分保证
for(i=1;i<=m;i++){
if(dp[i][n]==dp[m][n])break;
}
minn=i;