50pts求条
  • 板块P1544 三倍经验
  • 楼主crean_
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/26 17:32
  • 上次更新2024/5/26 19:57:37
查看原帖
50pts求条
921417
crean_楼主2024/5/26 17:32

50pts求条,请问各位大佬是不是有些转移方程写错了还是一些细节问题(

#include<bits/stdc++.h>
using namespace std;
long long dp[105][10500];
long long val[105][105];
int main(){
	int n,l;
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			scanf("%lld",&val[i][j]);
		}
	}
	dp[1][0]=val[1][1];
	dp[1][1]=val[1][1]*3;
	for(int i=2;i<=n;i++){
		for(int j=i;j>=1;j--){
			for(int k=min(i,l);k>=0;k--){
				int now=val[i][j];
				if(j==i){
					if(k==i) dp[i][k]=dp[i-1][k-1]+now*3;
					else if(k==0) dp[i][0]=dp[i-1][0]+now;
					else dp[i][k]=max(dp[i-1][k]+now,dp[i-1][k-1]+now*3);
				} 
				else if(j==1){
					if(k==i) dp[1][k]=dp[1][k-1]+now*3;
					else if(k==0) dp[1][0]=dp[1][0]+now;
					else dp[1][k]=max(dp[1][k]+now,dp[1][k-1]+now*3);
				}
				else{
					if(k==i) dp[j][k]=max(dp[j][k-1]+now*3,dp[j-1][k-1]+now*3);
					else if(k==0) dp[j][0]=max(dp[j][0]+now,dp[j-1][0]+now);
					else dp[j][k]=max(max(dp[j][k]+now,dp[j][k-1]+now*3),max(dp[j-1][k]+now,dp[j-1][k-1]+now*3));
				}
			//	printf("i:%d j:%d k:%d dp[j][k]:%lld\n",i,j,k,dp[j][k]);
			}
		}
	}
	long long ans=-3e9;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=l;j++){
			ans=max(ans,dp[i][j]);
		}
	}
	printf("%lld",ans);
}
2024/5/26 17:32
加载中...