P1473用特判AC的疑惑
查看原帖
P1473用特判AC的疑惑
1017537
__yxfg__楼主2024/11/25 21:07

tag 标识的那一行为什么不加只有40pts? 加了就AC

#include<bits/stdc++.h>
using namespace std;

const int N = 110,M = 15;

void file(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
}

int n,m;
int a[N],b[N];
long long dp[2][M][N][N];
long long minn = 0x3f3f3f3f3f3f3f3f,maxn = 0;

int main(){
//	file();
	scanf("%d%d",&n,&m);
	for(int i = 1;i<=n;i++){
		scanf("%d",&a[i]);
		a[i+n]=a[i]=(a[i]%10+10)%10;
	}b[0] = a[0];
	for(int i = 1;i<=2*n;i++){
		b[i] = b[i-1]+a[i];
	}
	memset(dp[0],0x3f,sizeof dp[0]);
	for(int i = 1;i<=2*n;i++){
		for(int j = max(1,i-n+1);j<=i;j++){
			dp[1][1][j][i] = dp[0][1][j][i] = ((b[i]-b[j-1])%10+10)%10;
		}
	}
	for(int pt = 2;pt<=m;pt++){
//		dp[0][pt][st][sp] = min self dp[0][pt-1][st][k]*dp[0][1][k+1][sp];// 状态转移
//		dp[1][pt][st][sp] = max self dp[1][pt-1][st][k]*dp[1][1][k+1][sp];// 状态转移
		for(int i = pt;i<=2*n;i++){
			for(int j = max(1,i-n+1);j<=i-pt+1;j++){
				for(int k = j;k<i;k++){
					dp[0][pt][j][i] = min(dp[0][pt][j][i],dp[0][pt-1][j][k]*dp[0][1][k+1][i]);
					dp[1][pt][j][i] = max(dp[1][pt][j][i],dp[1][pt-1][j][k]*dp[1][1][k+1][i]);
				}
			}
		}
	}
	for(int i = 1;i<=n;i++){
		minn = min(minn,dp[0][m][i][i+n-1]);
		maxn = max(maxn,dp[1][m][i][i+n-1]);
	}
	if(minn<0)minn = 0;// tag
	printf("%d\n%d",minn,maxn);
	return 0;
}


2024/11/25 21:07
加载中...