0分求调
查看原帖
0分求调
768270
__why楼主2024/1/25 08:46

最大值对了,但是最小值没过,不知道哪里出了问题,答案是负数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=205;
int a[maxn],f1[maxn][maxn][maxn],f2[maxn][maxn][maxn],sum[maxn];
int mod(int x){
	return (x%10+10)%10;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i = 1;i <= n;i++)cin>>a[i],a[i+n]=a[i];
	for(int i = n;i <= 2*n;i++)sum[i]=sum[i-1]+a[i];
    for (int l=1;l<=2*n;l++)
    	for (int r=l;r<=2*n;r++)
    		f1[l][r][1]=f2[l][r][1]=mod(sum[r]-sum[l-1]);
    memset(f1,0x3f,sizeof f1);
	for(int k = 2;k <= m;k++){
		for(int i = 1 ;i<=2*n;i++){
			for(int j = i+k-1;j <= 2*n;j++){
				for(int duan = i+1; duan < j ; duan ++){
					f1[i][j][k]=min(f1[i][j][k],f1[i][duan][k-1]*mod(sum[j]-sum[duan]));
					f2[i][j][k]=max(f2[i][j][k],f2[i][duan][k-1]*mod(sum[j]-sum[duan]));
				}
			}
		}
	}
	int ans1=0,ans2=0x3f3f3f3f;
	for(int i = 1; i <= n;i++){
		ans1 = max(ans1, f2[i][i+n-1][m]);
		ans2 = min(ans2, f1[i][i+n-1][m]);
	}
	cout << ans2 << endl;
	cout << ans1 ;
	return 0;
}

2024/1/25 08:46
加载中...