4978:宠物小精灵之收服（0

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]; 123456789

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