P1043 [NOIP2003 普及组] 数字游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
- 化环为链 开两倍空间,求答案时遍历一遍
- big small[left][right]代表从乐left到right的最优解,题意还有分割成m块,那么再加一维
- modd 要求取模后全为非负数 :
((x%10)+10)%10
- 遍历分割块数,再遍历左右端点,再遍历分割点,内部看能否更新为前段和后段的乘积,前段是由dp值可以直接得到的,后段由前缀和求得
// 4 2
// 4
// 3
// -1
// 2
// https://www.luogu.com.cn/problem/P1043
#include <bits/stdc++.h>
using namespace std;
#define N 1e5
#define INF 2147483647
#define MAX 1000
int big[MAX][MAX][15], small[MAX][MAX][15];
int orign[MAX];
int n, m;
inline int modd(int x)
{
return (x % 10 + 10) % 10;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
scanf("%d", orign + i), orign[i + n] = orign[i];
for (int i = 1; i <= 2 * n; i++)
orign[i] += orign[i - 1];
for (int i = 1; i <= 2 * n; i++)
for (int j = i; j <= 2 * n; j++)
big[i][j][1] = small[i][j][1] = modd(orign[j] - orign[i - 1]);
for (int sps = 2; sps <= m; sps++)
for (int left = 1; left <= 2 * n; left++)
for (int right = left + sps - 1; right <= 2 * n; right++)
small[left][right][sps] = INF;
for (int sps = 2; sps <= m; sps++)
for (int left = 1; left <= 2 * n; left++)
for (int right = left + sps - 1; right <= 2 * n; right++)
for (int k = left + sps - 2; k < right; k++)
big[left][right][sps] = max(big[left][right][sps], big[left][k][sps - 1] * modd(orign[right] - orign[k])), small[left][right][sps] = min(small[left][right][sps], small[left][k][sps - 1] * modd(orign[right] - orign[k]));
int max_ans = 0, min_ans = INF;
for (int i = 1; i <= n; i++)
max_ans = max(max_ans, big[i][i + n - 1][m]), min_ans = min(min_ans, small[i][i + n - 1][m]);
cout << min_ans << endl << max_ans;
}
标签:10,遍历,游戏,int,MAX,right,define,数字 From: https://www.cnblogs.com/Wang-Xianyi/p/16639917.html