2794_dark_dp

发布于 2017-10-26  839 次阅读

题目描述

LichKing 希望收集邪恶的黑暗力量，并依靠它称霸世界。 
世间的黑暗力量被描述成一个长度为N 的非负整数序列{Ai}，每次它可以选择这个序列中的两个相邻的正整数，让他们的值同时减一并获得一点邪恶力量，直到不存在满足条件的数。 
然而你不希望他能够得逞，所以你会使得他收集的能量尽可能少。

 

思路

设设f[i]表示到第i个数合法，且第i个数减为0

#include 
#include 
#include 
using namespace std;
#define N 500001
#define fill(x, y) memset(x, y, sizeof(x))
#define INF 0x7f7f7f7f
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
int a[N];
int n;
inline int read()
{
	int x = 0, p = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') p = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();}
	return x * p;
}
int f[N];
int main()
{
	n = read();
	for (int i = 1; i <= n; i++)
		a[i] = read();
	fill(f, INF);
	f[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		f[i] = a[i] + f[i - 1];
		if (n >= 2) f[i] = min(f[i], f[i - 2] + a[i]);
		if (n >= 3) f[i] = min(f[i], f[i - 3] + max(a[i - 1], a[i]));
	}
	printf("%d\n", min(f[n - 1], f[n]));
}

　　

]]>