A题 Game
题目大意：有3台电脑编号为1、2、3，n个任务，每个任务指定要在编号为i的电脑上完成，每个任务还有一些前置任务，必须完成该任务的前置任务才能完成该任务。
你可以选择以任意一台电脑为起点，每完成一个任务消耗1时间，在电脑间移动的花费如下
1->2 cost:1
1->3 cost:2
2->3 cost:1
2->1 cost:2
3->1 cost:1
3->2 cost:2
求完成所有任务的最小花费。
题解：仔细观察在电脑间移动的花费可以发现，每次向编号递增的方向移动总是比向递减的方向移动更好，所以移动路线总是会按照1->2->3->1->2->3的顺序进行。
那么我们可以确定一个很简单的策略：
选编号为i的电脑为起点(1 <= i <= 3)先完成能在电脑i上完成的所有工作，然后前往下一个点，如此重复直到完成所有任务即可。
View Code
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <set> #include <vector> #include <queue> #include <stack> #include <cmath> #include <map> using namespace std; #define INF 0x73737373 #define EPS 1e-8 #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 int pos[205], n, ret; vector<int> pre[205]; bool vis[205]; bool pre_check(int index) { for(int i = 0; i < pre[index].size(); i++) if(!vis[pre[index][i]])return false; return true; } bool all_complete() { for(int i = 1; i <= n; i++)if(!vis[i])return false; return true; } void work(int now, int cost) { while(true) { bool find = false; for(int i = 1; i <= n; i++) { if(vis[i])continue; if(pre_check(i) && pos[i] == now) { vis[i] = true; find = true; cost++; } } if(!find)break; } if(all_complete()) { ret = min(ret, cost); return; } work((now % 3) + 1, cost + 1); } int main() { scanf("%d", &n); for(int i = 1; i <= n; i++)scanf("%d", &pos[i]); for(int i = 1; i <= n; i++) { int num; scanf("%d", &num); for(int j = 1; j <= num; j++) { int a; scanf("%d", &a); pre[i].push_back(a); } } ret = INF; for(int i = 1; i <= 3; i++) { memset(vis, false, sizeof(vis)); vis[0] = true; work(i, 0); } printf("%d\n", ret); return 0; }
B题 Numbers
题目大意：给一个数字n，和一个含有十个数字的数组a，要求计算出符合下列条件的正整数的个数条件：1.该数的长度不能超过n
2.该数不能有前导0
3.该数包含数字i的个数必须大于等于a[i]
题解：数位dp
我们用dp[len][j]来表示 长度为 len 使用数字 j - 9 能组合出的符合条件的数的数目
状态转移如下：
当 j == 9时，
即各位数字只能填9，那么当a[9] <= len时，dp[len][9]为1，否则dp[len][9]为0
当1 < j < 9时，
长度为 len-1 的数字共有 len个位置可以填数，我们可以把数字 j 填在其中任意一个地方，
由于题目要求数字j必须有a[j]个
所以我们可以枚举数字j有k个(a[i] <= k <= len)，那么这k个数字一共有C(len, k)种填法，
故状态转移方程为 dp[len][j] = sum(dp[len-1][j+1] * c[len][k]) a[j] <= k <= len
当j == 0时
这种情况和1 < j < 9时很接近，唯一的区别是0不能填在这个数字的开头，
所以长度为len的数字只有len个位置可以填
故dp[len][0] = sum(dp[len-1][1] * c[len-1][k]) a[0] <= k <= len
最后的答案为dp[i][0] 1 <= i <= n
View Code
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <set> #include <vector> #include <queue> #include <stack> #include <cmath> #include <map> using namespace std; #define INF 0x73737373 #define EPS 1e-8 #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 const int mod = 1e9 +7; int a[10]; __int64 c[105][105]; __int64 dp[105][10]; int main() { int len; scanf("%d", &len); for(int i = 0; i < 10; i++)scanf("%d", &a[i]); for(int i = 0; i <= len; i++) { c[i][0] = 1; for(int j = 1; j <= i; j++) c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod; } for(int l = 0; l <= len; l++) { dp[l][9] = l >= a[9]? 1 : 0; for(int j = 8; j >= 1; j--) for(int i = a[j]; i <= l; i++) dp[l][j] = (dp[l][j] + dp[l-i][j+1] * c[l][i]) % mod; for(int i = a[0]; i <= l; i++) dp[l][0] = (dp[l][0] + dp[l-i][1] * c[l-1][i]) % mod; } __int64 ret = 0; for(int i = 1; i <= len; i++) ret = (ret + dp[i][0]) % mod; printf("%I64d\n", ret); return 0; }