P1541 [NOIP2010 提高组] 乌龟棋

本文主要是介绍P1541 [NOIP2010 提高组] 乌龟棋，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

单向前进，每个点有权值，要求路径权值和最大。这不是显然的DP。但是这题对前进的步伐有四种，每种还有次数限制。。这就不好搞。朴素点的就是开四维DP。然后枚举，从前往后枚举。再看一下数据，还真的是。。

#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
#define drp(i,j,k) for(register int i(j);i>=k;--i)
using namespace std;
typedef long long lxl;
template<typename T>
inline T  max(T &a, T &b) {
	return a > b ? a : b;
}
template<typename T>
inline T  min(T &a, T &b) {
	return a < b ? a : b;
}

inline char gt() {
	static char buf[1 << 21], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void  read(T &x) {
	register char ch = gt();
	x = 0;
	int w(0);
	while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt();
	while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt();
	w ? x = ~(x - 1) : x;
}
template <typename T>
inline void out(T x) {
	if(x < 0) x = -x, putchar('-');
	char ch[20];
	int num(0);
	while(x || !num) ch[++num] = x % 10 + '0', x /= 10;
	while(num) putchar(ch[num--]);
	putchar('\n');
}
const int N = 407;
const int M = 127;
int n, m, a[N], num[N];
int f[47][47][47][47];
int main() {
	read(n);
	read(m);
	rep(i, 1, n) {
		read(a[i]);
	}
	rep(i, 1, m) {
		int x;
		read(x);
		num[x]++;
	}
	f[0][0][0][0]=a[1];
    rep(i,0,num[1])
    rep(j,0,num[2])
    rep(k,0,num[3])
    rep(h,0,num[4]){
    	int pos=1+i+2*j+3*k+4*h;
    	
    	if(i) f[i][j][k][h]=max(f[i][j][k][h],f[i-1][j][k][h]+a[pos]);
    	if(j) f[i][j][k][h]=max(f[i][j][k][h],f[i][j-1][k][h]+a[pos]);
    	if(k) f[i][j][k][h]=max(f[i][j][k][h],f[i][j][k-1][h]+a[pos]);
    	if(h) f[i][j][k][h]=max(f[i][j][k][h],f[i][j][k][h-1]+a[pos]);
	}
     out(f[num[1]][num[2]][num[3]][num[4]]);
	return 0;
}

这篇关于P1541 [NOIP2010 提高组] 乌龟棋的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！