25分dp求调
查看原帖
25分dp求调
768270
__why楼主2023/10/17 18:50

为什么是25分啊,不明白

#include<bits/stdc++.h>
using namespace std;
const int maxt = 105,maxn = 105,maxm = 1005;
int dp[maxt*maxn];//dp_i_j 表示第i天在持有j个物品时的最大金币数 
int a[maxt][maxn];
bool cmp(int a,int b){
	return a>b;
}
int main(){
	int t,n,m,money = 0;
	cin>>t>>n>>m;
	for(int i = 1;i<=t;i++){
		for(int j = 1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	money = m;//表示今天的最大金币数 
	for(int i = 1;i<=t;i++){
		memset(dp,-0x3f3f,sizeof(dp));
		dp[money] = money;
		for(int j = 1;j<=n;j++){
			for(int k = money;k>=a[i][j];k--){
				dp[k-a[i][j]] = max(dp[k]-a[i][j],dp[k]+a[i+1][j]-a[i][j]);
			}
		}
		int Max = -0x3f;
		for(int j = 1;j<=money;j++){
			Max = max(Max,dp[j]);
		}
		money = Max;
	}
	cout<<money; 
}
2023/10/17 18:50
加载中...