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的卡路里
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
* File: a.cpp
* Create Date: 2014-05-21 23:33:25
* Descripton:
*/
#include
#include
#include
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
* File: b.cpp
* Create Date: 2014-05-21 23:43:23
* Descripton:
*/
#include
#include
#include
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
* File: c.cpp
* Create Date: 2014-05-22 00:20:28
* Descripton:
*/
#include
#include
#include
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;
}
