程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu4719¡ª¡ªOh My Holy FFF

hdu4719¡ª¡ªOh My Holy FFF

編輯：C++入門知識

hdu4719¡ª¡ªOh My Holy FFF

Oh My Holy FFF

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 626 Accepted Submission(s): 147

Problem Description N soldiers from the famous "*FFF* army" is standing in a line, from left to right.

 o   o   o   o   o   o   o   o   o   o   o   o   o   o   o   o   o   o
/F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\ /F\
/ \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \

You, as the captain of *FFF*, want to divide them into smaller groups, but each group should still be continous in the original line. Like this:

 o   o   o  |  o   o   o   o  |  o   o   o   o   o   o  |  o   o   o   o   o
/F\ /F\ /F\ | /F\ /F\ /F\ /F\ | /F\ /F\ /F\ /F\ /F\ /F\ | /F\ /F\ /F\ /F\ /F\
/ \ / \ / \ | / \ / \ / \ / \ | / \ / \ / \ / \ / \ / \ | / \ / \ / \ / \ / \

In your opinion, the number of soldiers in each group should be no more than L.
Meanwhile, you want your division be "holy". Since the soldier may have different heights, you decide that for each group except the first one, its last soldier(which is the rightmost one) should be strictly taller than the previous group's last soldier. That is, if we set bi as the height of the last soldier in group i. Then for i >= 2, there should be b_i > b_i-1.
You give your division a score, which is calculated as

, b₀ = 0 and 1 <= k <= M, if there are M groups in total. Note that M can equal to 1.
Given the heights of all soldiers, please tell us the best score you can get, Z†·Ÿ"http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vciBkZWNsYXJlIHRoZSBkaXZpc2lvbiBhcyBpbXBvc3NpYmxlLgogCjxicj4KSW5wdXQKVGhlIGZpcnN0IGxpbmUgaGFzIGEgbnVtYmVyIFQgKFQgPD0gMTApICwgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuPGJyPgpGb3IgZWFjaCB0ZXN0IGNhc2UsIGZpcnN0IGxpbmUgaGFzIHR3byBudW1iZXJzIE4gYW5kIEwgKDEgPD0gTCA8PSBOIDw9IDEwPHN1cD41PC9zdXA+KSwgYXMgZGVzY3JpYmVkIGFib3ZlLjxicj4KVGhlbiBjb21lcyBhIHNpbmdsZSBsaW5lIHdpdGggTiBudW1iZXJzLCBmcm9tIEgxIHRvIEhuLCB0aGV5IGFyZSB0aGUgaGVpZ2h0IG9mIGVhY2ggc29sZGllciBpbiB0aGUgbGluZSwgZnJvbSBsZWZ0IHRvIHJpZ2h0LiAoMSA8PSBIPHN1Yj5pPC9zdWI+IDw9IDEwPHN1cD41PC9zdXA+KQogCjxicj4KT3V0cHV0CkZvciB0ZXN0IGNhc2UgWCwgb3V0cHV0IA=="Case #X: " first, then output the best score.
Sample Input

Sample Output

Case #1: 31
Case #2: No solution

Source 2013 ACM/ICPC Asia Regional Online ¡ª¡ª Warmup2
Recommend

Ïß¶ÎÊ÷dp
dp[i] = max(dp[j] - arr[j] + arr[i] * arr[i])

ÕâÌâÐèÒª´ÓÐ¡µÄ¿ªÊ¼´¦Àí£¬ÒòÎªÐ¡µÄ²»ÊÜ´óµÄÓ°Ïì£¬ËùÒÔÏÈ´¦ÀíÃ»¹ØÏµ£¬µ«ÊÇÈç¹ûÓöµ½ÓÐÏàÍ¬µÄ¸ß¶ÈµÄµãj, iÊ±£¬ÎÒÃÇÐèÒªÏÈ´¦ÀíÅÅÔÚºóÃæµÄi£¬ÒòÎªÈç¹ûÏÈ´¦ÀíÇ°ÃæµÄj£¬¶øÇÒºÜ²»ÇÉ¸ÕºÃjÓÐ×î´ó值£¬ÄÇÃ´´¦ÀíiµÄÊ±ºò¾Í»á²éµ½ÄÇ¸ö值£¬µ«ÊÇÕâÆäÊµÊÇ·Ç·¨µÄ£»·´Ö®ÎÒÃÇÏÈ´¦ÀíºóÃæµÄi£¬´ËÊ±jÃ»ÓÐ²åÈëµ½Ïß¶ÎÊ÷ÉÏ£¬ËùÒÔi²»ÊÜÓ°Ïì£¬¶ø´¦ÀíÇ°ÃæµÄjµÄÊ±ºò£¬Ò²ÊÇÍù×óÕÒ£¬ËùÒÔ²»ÊÜºóÃæµÄiµÄÓ°Ïì£¬²éÑ¯µÄÊ±ºòÖ»Òª±£Ö¤²éÑ¯Çø¼ä³¤¶È²»´óÓëd¾ÍÐÐÁË

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 100010;
int n, d;
int arr[N];
__int64 dp[N];
struct data
{
	int x, pos;
}sorting[N];

struct node
{
	int l, r;
	__int64 val;
}tree[N << 2];

int cmp(data a, data b)
{
	if (a.x != b.x)
	{
		return a.x < b.x;
	}
	return a.pos > b.pos;
}

void build(int p, int l, int r)
{
	tree[p].l = l;
	tree[p].r = r;
	tree[p].val = -1;
	if (l == r)
	{
		return;
	}
	int mid = (l + r) >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
}

void update(int p, int pos, __int64 val)
{
	if (tree[p].l == tree[p].r)
	{
		tree[p].val = val;
		return;
	}
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (pos <= mid)
	{
		update(p << 1, pos, val);
	}
	else
	{
		update(p << 1 | 1, pos, val);
	}
	tree[p].val = max(tree[p << 1].val, tree[p << 1 | 1].val);
}

__int64 query(int p, int l, int r)
{
	if (l <= tree[p].l && r >= tree[p].r)
	{
		return tree[p].val;
	}
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (r <= mid)
	{
		return query(p << 1, l, r);
	}
	else if (l > mid)
	{
		return query(p << 1 | 1, l, r);
	}
	else
	{
		return max(query(p << 1, l, mid), query(p << 1 | 1, mid + 1, r));
	}
}

int main()
{
	int t, icase = 1;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d", &n, &d);
		memset (dp, -1, sizeof(dp));
		arr[0] = 0;
		dp[0] = 0;
		for (int i = 1; i <= n; ++i)
		{
			scanf("%d", &arr[i]);
			sorting[i].x = arr[i];
			sorting[i].pos = i;
		}
		sort (sorting + 1, sorting + n + 1, cmp);
		build(1, 0, n);
		update(1, 0, 0);
		for (int i = 1; i <= n; ++i)
		{
			int j = sorting[i].pos;
			__int64 cur = query(1, max(0, j - d), j - 1);
			if (cur >= 0)
			{
				dp[j] = cur + (__int64)arr[j] * arr[j];
				update(1, j, dp[j] - arr[j]);
			}
		}
		printf("Case #%d: ", icase++);
		if (dp[n] <= 0)
		{
			printf("No solution\n");
		}
		else
		{
			printf("%I64d\n", dp[n]);
		}
	}
	return 0;
}