题意:
n个技能能，每个技能可以升级到m，升级的时候需要花费(可能是正可能是负的),若所有的技能全部升级成功则有额外的奖励(可能为正，可能为负)
思路:对于第i的技能等级有两种情况，要么前n个技能全部升级到i-1的等级再加上i以后的最优解(但是n个技能不能全部升级到i级)，这要就涵盖了所有的可能性，然后暴力跑出最优解
#include <stdio.h> #include<string.h> #include<algorithm> typedef long long ll; #define INF 0xFFFFFFFFFFFFFF #define maxn 1010 using namespace std; ll a[maxn][maxn],reward[maxn],dp[maxn][maxn],all[maxn]; int main(int argc, char *argv[]) { int t,ca=1; scanf("%d",&t); while(t--) { int n,m; scanf("%d %d",&n,&m); int i,j; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%lld",&a[i][j]); } } for(i=1;i<=n;i++) { dp[i][m+1]=0; for(j=m;j>=1;j--) { dp[i][j]=max(0ll,dp[i][j+1]-a[i][j]); //printf("%d ",dp[i][j]); } //printf("\n"); } for(i=1;i<=m;i++) { scanf("%lld",&reward[i]); } all[0]=0; for(i=1;i<=m;i++) { all[i]=all[i-1]+reward[i]; for(j=1;j<=n;j++) { all[i]-=a[j][i]; } } ll num,ans=0,sum,minn; for(i=1;i<=m;i++) { sum=num=0; minn=INF; for(j=1;j<=n;j++) { sum+=dp[j][i]; if(dp[j][i]) { num++; minn=min(minn,dp[j][i]); } } if(num==n) { sum-=minn; } ans=max(ans,sum+all[i-1]); } printf("Case #%d: ",ca++); printf("%lld\n",max(ans,all[m])); } return 0; }
