欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

NOIP普及组2003 数字游戏 解题报告

程序员文章站 2022-05-14 20:20:09
...

题目链接

LGOJ P1043 数字游戏

解题思路

区间DP
最大值与最小值求解过程相似,下面先讨论最大值的情况

本题求解过程:
1)几乎所有一个有环的序列都要用到破环成链的做法。采用这种做法后,最后的答案寻储需要注意
2)由于本题要求区间和,可以先预处理前缀和。
3)接下来就是DP了
f[l][r][i]f[l][r][i]表示将区间[l,r]l,r]分成ii段可得的最大的kk
所以,我们只要从小到大枚举段数ii(由于f[..][..][i]f[..][..][i]的状态是由f[..][..][i1]f[..][..][i-1]推来的,所以接下来我们没必要枚举区间长度),然后分别枚举左端点、右端点、断点即可。
具体看代码

详细代码

#define USEFASTERREAD 1 

#define rg register
#define inl inline
#define DEBUG printf("[Passing [%s] in line %d.]\n", __func__, __LINE__)
#define putline putchar('\n')
#define putsp putchar(' ')
#define Rep(a, s, t) for(rg int a = s; a <= t; a++)
#define Repdown(a, t, s) for(rg int a = t; a >= s; a--)
typedef long long ll;
#include<cstdio>

#if USEFASTERREAD
char In[1 << 20], *ss = In, *tt = In;
#define getchar() (ss == tt && (tt = (ss = In) + fread(In, 1, 1 << 20, stdin), ss == tt) ? EOF : *ss++)
#endif
struct IO {
	void RS() {freopen("test.in", "r", stdin), freopen("test.out", "w", stdout);} 
	template<typename T> inline IO r(T& x)const	{
	    x = 0; T f = 1; char ch = getchar();
	    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
	    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + int(ch - '0');
	    x *= f; return *this;
	}
	template<typename T> inline IO w(T x)const {
	    if(x < 0) {putchar('-'); x = -x;}
	    if(x >= 10) w(x / 10);
	    putchar(x % 10 + '0'); return *this;
	}
	template<typename T> inline IO wl(const T& x)const {w(x), putline; return *this;}
	template<typename T> inline IO ws(const T& x)const {w(x), putsp; return *this;}
	inline IO l() {putline; return *this;}
	inline IO s() {putline; return *this;}
}io;
template<typename T> inline T Max(const T& x, const T& y) {return y < x ? x : y;}
template<typename T> inline T Min(const T& x, const T& y) {return y < x ? y : x;}
template<typename T> inline void Swap(T& x, T& y) {T tmp = x; x = y; y = tmp;}
template<typename T> inline T Abs(const T& x) {return x > 0 ? x : -x;} 
#include<cstring>
const int INF = 0x3f3f3f3f;
const int MAXN = 105;
const int MAXM = 10;
int n, m;
int N;
int A[MAXN];
int sum[MAXN];
int f[MAXN][MAXN][MAXM];//f[l][r][i]将区间[l,r]分成i段可得的最大的k 
int g[MAXN][MAXN][MAXM];//g[l][r][i]将区间[l,r]分成i段可得的最小的k
int mod(int a) {
	return (a % 10 + 10) % 10;
}
int main() {
    //io.RS();
    io.r(n).r(m);
    for(rg int i = 1; i <= n; i++) {
		io.r(A[i]);
		A[i + n] = A[i];
	}
	N = 2 * n;
	for(rg int i = 1; i <= N; i++) 
		sum[i] = sum[i - 1] + A[i];
	memset(g, 0x3f, sizeof g);
	for(rg int l = 1; l <= N; l++)
		for(rg int r = l; r <= N; r++)
			f[l][r][1] = g[l][r][1] = mod(sum[r] - sum[l - 1]); 
	for(rg int i = 2; i <= m; i++)
		for(rg int l = 1; l <= N; l++)
			for(rg int r = l + i - 1; r <= N; r++)
				for(rg int k = l + i - 2; k < r; k++) {//断点分成了[l,k],[k+1,r] 
					f[l][r][i] = Max(f[l][r][i], f[l][k][i - 1] * mod(sum[r] - sum[k]));
					g[l][r][i] = Min(g[l][r][i], g[l][k][i - 1] * mod(sum[r] - sum[k])); 
				}
	int mx = 0, mn = INF;
	for(rg int i = 1; i <= n; i++) {
		mx = Max(mx, f[i][i + n - 1][m]);
		mn = Min(mn, g[i][i + n - 1][m]);
	}
	io.wl(mn).wl(mx);
    return 0;
}
相关标签: OI 题解