Codeforces Round #247 (Div. 2) ABC_html/css_WEB-ITnose

Codeforces Round #247 (Div. 2)

http://codeforces.com/contest/431
The codes have been released: https://github.com/illuz/ WayToACM/tree/master/CodeForces/431

A - Black Square

Question address

Question meaning:
Don’t step on white when playing Jury There are four areas in the game. Jury clicks on each area to consume AI calories. He gives the sequence of stepping on the white blocks and asks how many calories are consumed.

Analysis:
Simulated water problem..

Code:

/**  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

Question address

Question meaning:
5 students line up, in each case of a certain queuing method, No. 2i-1 The individual and the 2nd person will talk. During the conversation, the conversation between the i-th and j-th people will produce the joy (base) value of g[i][j] g[j][i], and find the maximum joy value.

Analysis:
At first I thought the number of people was undecided, so I hesitated for a while...
Directly use next_permutation violence, 5! is acceptable.

Code:

/**  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

Question address

Question meaning:
An infinite k-tree is defined as follows:
Each node has k branches, and the edge weight of the i-th branch is i .
Ask how many paths there are in the k-tree. There is at least one edge whose weight is not less than d, and the sum of the path edges is n.

Analysis:
I didn’t type it out during the game (too weak orz). After the game I found something was wrong...
You can use dp for this question, because it is an infinite tree, so the root The removal of nodes is the same as the removal of each node, but one more factor is needed to transfer it to a sub-problem, which is that the conditional edge must be <=d, so we can open another one-dimensional storage to see if conditions are required.
See the code specifically...

Code:

/**  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;}