时间:2021-07-01 10:21:17 帮助过:16人阅读
http://codeforces.com/contest/431
代码均已投放:https://github.com/illuz/WayToACM/tree/master/CodeForces/431
题目地址
题意:
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;}
题目地址
题意:
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;}
题目地址
题意:
一颗无限的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;}