Codeforces ラウンド #247 (ディビジョン 2) ABC_html/css_WEB-ITnose

Codeforces Round #247 (Div. 2)

http://codeforces.com/contest/431
コードはリリースされました: https://github.com/illuz/WayToACM/tree/master/CodeForces/431

A - Black Square

質問アドレス

質問の意味:
ジュリーがプレイしている間は白いブロックを踏まないでください ゲームには 4 つのエリアがあり、各エリアをクリックすることで 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 - シャワーライン

質問アドレス

質問の意味:
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 ツリーにパスがいくつあるかを尋ねます。少なくとも 1 つのエッジの重みが d 以上であり、パスのエッジの合計は n です。

分析:
競技中に入力しませんでした (弱すぎ orz) 試合後、何かが間違っていることに気づきました...
この質問は無限ツリーなので、dp を使用できます。ルート ノードと各ノードは同じですが、それをサブ問題に転送するには、もう 1 つの要素が必要です。つまり、条件付きエッジが <=d である必要があるため、別の 1 次元ストレージを開いて、次のことを確認できます。条件が必要です。
具体的にコードをご覧ください...

コード:

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