Codeforces Round #247 (Div. 2)

http://codeforces.com/contest/431 

代码均已投放：https://github.com/illuz/WayToACM/tree/master/CodeForces/431

---

A - Black Square

题目地址

题意： 

Jury玩别踩白块，游戏中有四个区域，Jury点每一个区域要消耗ai的卡路里，给出踩白块的序列，问要消耗多少卡路里。

分析： 

模拟水题..

代码：

/*

*  Author:      illuz <iilluzen[at]gmail.com>

*  File:        a.cpp

*  Create Date: 2014-05-21 23:33:25

*  Descripton:

*/

#include <cstdio>

#include <iostream>

#include <string>

using namespace std;

int a[5], ans;

string s;

int main()

{

	for (int i = 1; i <= 4; i++)

		cin >> a[i];

	cin >> s;

	for (int i = 0; i < s.length(); i++)

		ans += a[s[i] - '0'];

	cout << ans << endl;

	return 0;

}

---

B - Shower Line

题目地址

题意： 

5个学生排队，某一个排队方式的每个情况下，第2i-1个人和第2个人会交谈。交谈时，第i和第j个人的交谈会产生g[i][j] + g[j][i]的欢乐（搞基）值，求中最大的欢乐值。

分析： 

刚開始还以为人数没定，犹豫了一会... 

直接用next_permutation暴力，5!是能够接受的。

代码：

/*

*  Author:      illuz <iilluzen[at]gmail.com>

*  File:        b.cpp

*  Create Date: 2014-05-21 23:43:23

*  Descripton:

*/

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 5;

char ch;

int g[N][N], mmax;

int a[5] = {0, 1, 2, 3, 4};

int main()

{

	int i = 0, j = 0;

	for (int i = 0; i < 5; i++)

		for (int j = 0; j < 5; j++)

			scanf("%d", &g[i][j]);

	for (int i = 0; i < 5; i++)

		for (int j = i + 1; j < 5; j++) {

			g[j][i] = g[i][j] = g[i][j] + g[j][i];

		}

	do {

		mmax = max(mmax, g[a[0]][a[1]] + g[a[1]][a[2]] + g[a[2]][a[3]] * 2 + g[a[3]][a[4]] * 2);

	} while (next_permutation(a, a + 5));

	cout << mmax << endl;

	return 0;

}

---

C - k-Tree

题目地址

题意： 

一颗无限的k-tree，定义例如以下： 

每一个节点都有k个分支，第i个分支的边的权值为i。 

问在k-tree中有多少条路径，里面至少有一条边权值不小于d，且路径边的和为n。

分析： 

比赛时没敲出来（太弱orz），赛后发现有个地方错了... 

这题能够用dp，由于是无限的树，所以根节点下来和每一个节点下来是一样的，可是转移为子问题还须要一个因素，就是条件限定边必须<=d，所以我们能够再开一维存放是否须要条件限定。 

详细看代码...

代码：

/*

*  Author:      illuz <iilluzen[at]gmail.com>

*  File:        c.cpp

*  Create Date: 2014-05-22 00:20:28

*  Descripton:

*/

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

const int N = 110;

const int MOD = 1e9 + 7;

ll D[N][2];

int n, d, k;

ll dp(int r, bool b)

{

	if (D[r][b] != -1)

		return D[r][b];

	if (r == 0)

		return D[r][b] = b;

	D[r][b] = 0;

	for (int i = 1; i <= min(r, k); i++)

		if (b || i >= d)

			D[r][b] = (D[r][b] + dp(r - i, 1)) % MOD;

		else

			D[r][b] = (D[r][b] + dp(r - i, 0)) % MOD;

	return D[r][b];

}

int main()

{

	memset(D, -1, sizeof(D));

	scanf("%d%d%d", &n, &k, &d);

	cout << dp(n, 0) << endl;

	return 0;

}