又不好好写作业了……
差点忘了今天的ddl orz
要期末季了QAQ 不能再整天晃晃悠悠吊儿郎当的
A:UNIMODAL PALINDROMIC DECOMPOSITIONS
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
A sequence of positive integers is Palindromic if it reads the same forward and backward. For example:
23 11 15 1 37 37 1 15 11 23
1 1 2 3 4 7 7 10 7 7 4 3 2 1 1
A Palindromic sequence is Unimodal Palindromic if the values do not decrease up to the middle value and then (since the sequence is palindromic) do not increase from the middle to the end For example, the first example sequence above is NOT Unimodal Palindromic while the second example is.
A Unimodal Palindromic sequence is a Unimodal Palindromic Decomposition of an integer N, if the sum of the integers in the sequence is N. For example, all of the Unimodal Palindromic Decompositions of the first few integers are given below:
1: (1)
2: (2), (1 1)
3: (3), (1 1 1)
4: (4), (1 2 1), (2 2), (1 1 1 1)
5: (5), (1 3 1), (1 1 1 1 1)
6: (6), (1 4 1), (2 2 2), (1 1 2 1 1), (3 3),
(1 2 2 1), ( 1 1 1 1 1 1)
7: (7), (1 5 1), (2 3 2), (1 1 3 1 1), (1 1 1 1 1 1 1)
8: (8), (1 6 1), (2 4 2), (1 1 4 1 1), (1 2 2 2 1),
(1 1 1 2 1 1 1), ( 4 4), (1 3 3 1), (2 2 2 2),
(1 1 2 2 1 1), (1 1 1 1 1 1 1 1)
Write a program, which computes the number of Unimodal Palindromic Decompositions of an integer. - 输入
- Input consists of a sequence of positive integers, one per line ending with a 0 (zero) indicating the end.
- 输出
- For each input value except the last, the output is a line containing the input value followed by a space, then the number of Unimodal Palindromic Decompositions of the input value. See the example on the next page.
- 样例输入
-
2 3 4 5 6 7 8 10 23 24 131 213 92 0
- 样例输出
-
2 2 3 2 4 4 5 3 6 7 7 5 8 11 10 17 23 104 24 199 131 5010688 213 1055852590 92 331143
- 提示
- N < 250
- 来源
- Greater New York 2002
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 long long f[251][251]; 5 const int maxn = 250, maxk = 250; 6 int main(){ 7 int n; 8 memset(f,0,sizeof(f)); 9 for(int i = 1; i <= maxn; i++){ 10 f[i][i] = 1; 11 f[0][i] = 1; 12 } 13 for(int i = 1; i <= maxn; i++){ 14 for(int j = 1; j <= i; j++){ 15 f[i][j] = 1; 16 for(int k = j; k <= i/2; k++){ 17 f[i][j]+=f[i-2*k][k]; 18 } 19 } 20 } 21 /* 22 for(int i = 1; i <= 10; i++){ 23 for(int j = 1; j <= 10; j++){ 24 cout<<f[i][j]<<" "; 25 } 26 cout<<endl; 27 }*/ 28 while(1){ 29 cin>>n; 30 if(n == 0) break; 31 cout<<n<<" "<<f[n][1]<<endl; 32 33 } 34 return 0; 35 }
备注：还，有一点点成就感^ ^，四舍五入可以算是自己推出了状态转移方程了，跟网上的答案似乎有一点区别. 感觉就得多举几个例子，并且考虑在不同情况（比如奇数偶数），然后拆分看看。 用这道题来捋一下动归的做题思路。
这道题其实就是问给一个数n，将它拆分成一个先不严格上升再不严格下降的对称数列（Unimodal Palindromic ）有几种拆法。
动态规划首先要确定怎样定义一个状态。但这个就不能凭空想，需要推几个例子看看。其实盯着题目里给的例子也能看出来一些。
很容易想到，比如8拆成1-6-1吧，那么接下来还有一些拆法就是1-xxx-1，而xxx就是6的拆法。所以这就是可以分解的子问题：枚举首（尾）数字，然后呢，中间的数也不是随便一种拆法就能插进去的。再举个例子，比如8还可以拆成2-4-2，那么要满足先升后降的性质，在拆4时，就要保证首（尾）数字不小于2.
这样我们就可以来定义状态了，用f[n][k]来表示拆分数字n，并且首（尾）数字不小于k的拆法总数。最终结果就是f[n][1].
写出状态后，就尝试推导状态转移方程。
来试一个小点的数，比如5吧，有 (5), (1 3 1), (1 1 1 1 1)这三种拆法。 就相当于f[5][1]=f[5-1*2][1]=f[3][1]+1. 而f[3][1]=f[1][1]+1. f[5-1*2][1]就表示假设首尾拆出的数字是1，那么就从5里减掉首尾的两个1，那么也就是f[3][1]。
那么我们已经可以大概写出转移方程：
f[n][k] = 1+ sigma(f[n-2*j][j]), 可以直接看出的一个边界条件就是f[i][i]=1。要+1是要加本身这个数，也算是一种拆分方法。
那么j的取值范围是多少呢？再来试试6. 6有 (6), (1 4 1), (1 1 2 1 1), (1 2 2 1), ( 1 1 1 1 1 1)，(3 3),(2 2 2), 也就对应着j=1,2,3。现在也就可以看出，j的取值应当是从1到n/2. 其他的没有啥区别，但当j=3时，也就是（3，3）这种分法，对应的是f[0][3]，这个数应当等于1.
也就是说，另一个边界条件是f[0][i] = 1, 这个边界条件实际蕴含的含义是，偶数比奇数多了一种对半分的拆分方法，因为只有偶数才会出现n-2*j==0。对于5来说，5/2=2，首尾是2的话就没有办法拆分了，也就对应着f[5-2*2][2] = f[1][2]=0。
对于i≠0的情况，f[i][j]当j>i的时候肯定分法就是0.
完整的转移方程：
f[n][k] = 1+ sigma(f[n-2*j][j]) j=1,2,3,....,n/2. 边界条件 f[i][i]=1, f[0][i] = 1
递推顺序没啥好说的，就从小到大顺着推就行了。注意下枚举到j<=i就可以了，因为j>i肯定都是0.
把250以内的结果都预处理出来，这样对于每个输入直接输出就可以了。
我真是个小天才！
B:硬币
- 总时间限制:
- 1000ms
- 内存限制:
- 262144kB
- 描述
-
宇航员Bob有一天来到火星上，他有收集硬币的习惯。于是他将火星上所有面值的硬币都收集起来了，一共有n种，每种只有一个：面值分别为a1,a2… an。 Bob在机场看到了一个特别喜欢的礼物，想买来送给朋友Alice，这个礼物的价格是X元。Bob很想知道为了买这个礼物他的哪些硬币是必须被使用的，即Bob必须放弃收集好的哪些硬币种类。飞机场不提供找零，只接受恰好X元。
- 输入
- 第一行包含两个正整数n和x。（1 <= n <= 200, 1 <= x <= 10000)
第二行从小到大为n个正整数a1, a2, a3 … an （1 <= ai <= x) - 输出
- 第一行是一个整数，即有多少种硬币是必须被使用的。
第二行是这些必须使用的硬币的面值（从小到大排列）。 - 样例输入
-
5 18 1 2 3 5 10
- 样例输出
-
2 5 10
- 提示
- 输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付X元。
如果不存在必须被使用的硬币，则第一行输出0，第二行输出空行。
1 #include<cstring> 2 #include<iostream> 3 using namespace std; 4 int dp[205][10010]; 5 int ans[205][10010]; //ans数组表示在去掉a[i]币值之后，硬币能不能表示价格j 6 int a[205]; 7 int b[205]; 8 int main(){ 9 int n, x; 10 int cnt; 11 memset(dp, 0, sizeof(dp)); 12 memset(b, 0, sizeof(b)); 13 memset(a, 0, sizeof(a)); 14 cin>>n>>x; 15 for(int i = 1; i <= n; i++){ 16 cin>>a[i]; 17 } 18 dp[0][0] = 1; 19 for(int i = 1; i <= n; i++){ 20 for(int j = 0; j <= x; j++){ //必须从0开始循环 21 if(j-a[i]>=0) //因为这里，所以必须从0开始循环！ j-a[i]可能等于0 22 dp[i][j] = dp[i-1][j-a[i]] + dp[i-1][j]; 23 else 24 dp[i][j] = dp[i-1][j]; 25 } 26 } 27 cnt = 0; 28 for(int i = 1; i <= n; i++){ 29 for(int j = 0; j <= x; j++){ 30 if(j < a[i]) //一定不能取a[i] 31 ans[i][j] = dp[n][j]; //ans[i][j]表示不带第i种硬币凑成j的方法数 32 else //否则dp[i][j]表示可以包括a[i]也可以不包括a[i]，凑成j面值的方法数 33 ans[i][j] = dp[n][j] - ans[i][j-a[i]]; //ans[i][j-a[i]]表示不带a[i]可以凑成j-a[i]的方法总数，也就相当于必须含a[i]凑成j的方法数 34 if(ans[i][x] == 0){ 35 b[cnt ++] = a[i]; 36 } 37 } 38 cout<<cnt<<endl; 39 if(cnt == 0) 40 cout<<endl; 41 else 42 for(int i = 0; i < cnt; i++){ 43 cout<<b[i]<<" "; 44 } 45 return 0; 46 }
备注：这次的题都好难啊orz
原代码用了滚动数组，我想着改成二维数组更容易理解一些，结果还真帮助我理解了。
dp这个数组的推导利用了背包的思想。这没啥好说的，d[i][j]表示用前i种硬币凑出j的方法数。那么就包括用第i种硬币和不用第i种硬币两种可能。
其实dp这个数组就是为了得到dp[n][j]，也就是用n种硬币凑j的方法数。下面会用到。那块我最开始写错了，标黄行我写成了dp[i][j]，是因为还没理解这个思想。
ans这个数组太巧妙了，ans[i][j]表示不用第i种硬币凑出j的方法数，这个怎么推呢？其实这里应该算是状态转移方程。
前面说了，dp[n][j]既有含第i种硬币的，也有不含的。那么，就要从这里面刨掉含第i种硬币的方法数，也就是ans[i][j-a[i]]，为什么呢？
倒着想，假设d[i][j]表示含硬币i凑j的方法数，那么它和ans[i][j-a[i]] （不用硬币i，去凑j-a[i]）是等价的。 相当于从d[i][j]里刨掉了第i种硬币，因为j里是含a[i]的，所以j要减掉a[i]。
如果操作完发现这个ans[i][x]等于0，就说明不用这种硬币就凑不出来，说明这种硬币是必须有的orz
C:Charm Bracelet
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N(1 ≤ N≤ 3,402) available charms. Each charm iin the supplied list has a weight Wi(1 ≤ Wi≤ 400), a 'desirability' factor Di(1 ≤ Di≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M(1 ≤ M≤ 12,880).
Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
- 输入
- Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di - 输出
- Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
- 样例输入
-
4 6 1 4 2 6 3 12 2 7
- 样例输出
-
23
1 #include<cstring> 2 #include<iostream> 3 using namespace std; 4 int n, m; 5 int w[3500]; 6 int v[3500]; 7 int d[12900]; 8 int main(){ 9 memset(w,0,sizeof(w)); 10 memset(v,0,sizeof(v)); 11 memset(d,0,sizeof(d)); 12 cin>>n>>m; 13 for(int i = 1; i <= n; i++){ 14 cin>>w[i]>>v[i]; 15 } 16 for(int i = 1; i <= n; i++){ 17 for(int j = m; j >= w[i]; j--){ 18 d[j] = max(d[j], d[j-w[i]]+v[i]); 19 } 20 } 21 cout<<d[m]<<endl; 22 return 0; 23 }
备注：终于是01背包+滚动数组的大水题。记着没有d[0]=1了，别和上一题弄混。
D:课程大作业
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
小明是北京大学信息科学技术学院三年级本科生。他喜欢参加各式各样的校园社团。这个学期就要结束了，每个课程大作业的截止时间也快到了，可是小明还没有开始做。每一门课程都有一个课程大作业，每个课程大作业都有截止时间。如果提交时间超过截止时间X天，那么他将会被扣掉X分。对于每个大作业，小明要花费一天或者若干天来完成。他不能同时做多个大作业，只有他完成了当前的项目，才可以开始一个新的项目。小明希望你可以帮助他规划出一个最好的办法(完成大作业的顺序)来减少扣分。
- 输入
- 输入包含若干测试样例。
输入的第一行是一个正整数T，代表测试样例数目。
对于每组测试样例，第一行为正整数N（1 <= N <= 15）代表课程数目。
接下来N行，每行包含一个字符串S（不多于50个字符）代表课程名称和两个整数D（代表大作业截止时间）和C（完成该大作业需要的时间）。
注意所有的课程在输入中出现的顺序按照字典序排列。 - 输出
- 对于每组测试样例，请输出最小的扣分以及相应的课程完成的顺序。
如果最优方案有多个，请输出字典序靠前的方案。 - 样例输入
-
2 3 Computer 3 3 English 20 1 Math 3 2 3 Computer 3 3 English 6 3 Math 6 3
- 样例输出
-
2 Computer Math English 3 Computer English Math
- 提示
- 第二个测试样例, 课程完成顺序Computer->English->Math 和 Computer->Math->English 都会造成3分罚分, 但是我们选择前者,因为在字典序中靠前.
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 using namespace std; 5 const int maxx = 1 << 16; 6 int d[16]; //ddl 7 int t[16]; //需用时间 8 int sum[maxx];//当前做法下完成任务总用时 9 string name[16]; 10 string ans[maxx];//用来存储做法 11 int dp[maxx];//当前做法下的最少扣分 12 int f(int i, int j) { 13 return max(0, i - j); 14 } 15 int main() { 16 int T; 17 cin >> T; 18 while (T--){ 19 int N; 20 cin >> N; 21 for (int i = 0; i < N; i++){ 22 cin >> name[i]; 23 cin >> d[i]; 24 cin >> t[i]; 25 sum[1 << i] = t[i]; 26 } 27 for (int i = 1; i < 1<<N; i++){ 28 for (int j = 0; j < N; j++){ 29 if (i & (1 << j)) { //把一个1变成0肯定比原来的数小 30 sum[i] = sum[i ^ (1 << j)] + t[j]; //没有这种任务的时间+这种任务的时间 31 } 32 } 33 }//得到所有用时，下面开始更新扣分 34 for (int i = 0; i < 1<<N; i++){ 35 ans[i] = ""; 36 }//初始化答案串 37 dp[0] = 0; 38 for (int i = 1; i <1<<N ; i++){//枚举所有状态 39 for (int j = 0; j < N; j++){ 40 if (i & (1 << j) && (dp[i ^ (1 << j)] + f(sum[i], d[j]) <= dp[i] || ans[i] == "")) { 41 if (dp[i ^ (1 << j)] + f(sum[i], d[j]) < dp[i] || ans[i ^ (1 << j)] + name[j] + " " < ans[i] || ans[i] == "") { 42 ans[i] = ans[i ^ (1 << j)] + name[j] + " "; 43 } 44 dp[i] = dp[i ^ (1 << j)] + f(sum[i], d[j]); 45 } 46 } 47 } 48 cout << dp[(1 << N )- 1] << endl; 49 cout << ans[(1 << N) - 1] ; 50 } 51 return 0; 52 }
备注：又是一道大难题orz 我觉得这不是状压dp，就是枚举然后更新。
参考的博客里有这么一段话：
观察到这里每一时间选择什么课的罚分只由选课本身决定，所需要记录的只有前面的课程有哪些，而不是课程的顺序，这样就将一个n！的复杂度化为2n。
这也就是要预处理sum的原因，sum[state]表示在state状态下的总用时。
然后就开始枚举：
第一个if
if (i & (1 << j) && (dp[i ^ (1 << j)] + f(sum[i], d[j]) <= dp[i] || ans[i] == ""))
表示两种情况下需要更新dp：1.状态中包含第j个课程，并且不包含这个课程的dp+这个课程带来的罚时可以更小 2.ans为空
第二个if
if (dp[i ^ (1 << j)] + f(sum[i], d[j]) < dp[i] || ans[i ^ (1 << j)] + name[j] + "
" < ans[i] || ans[i] == "")
表示三种情况下需要更新ans：1.罚时严格更小 2.字典序更小（用到了字符串直接比较） 3.ans为空
就这样了！