描述
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
来源 G
reater New York 2002
- #include <iostream>
- #include <cstdio>
- #include <string.h>
- #include <algorithm>
- #include <stdlib.h>
- #include <math.h>
- using namespace std;
- const int maxn = 255;
- unsigned dp[maxn][maxn];
- int n, maxnow;
- void dpsolve() {
- for (int i = maxnow+1; i <= n; i++)
- {
- for (int plus=i/2;plus>=1;plus--)
- {
- dp[i][plus] = dp[i-2*plus][plus]+dp[i][plus+1];
- }
- }
- maxnow = n;
- printf("%d %u\n", n, dp[n][1]);
- }
- void init() {
- maxnow = 1;
- for (int i = 0; i <maxn; i++)dp[0][i] = 1;
- for (int i = 1; i < maxn; i++)
- for (int j = 0; j < maxn; j++)dp[i][j] = bool(j <= i);
- while (~scanf("%d", &n) && n) {
- if (n <= maxnow)printf("%d %u\n",n, dp[n][1]);
- else
- dpsolve();
- }
- }
- int main()
- {
- init();
- return 0;
- }
- View Code
解题思路:
拆分所需要的数, 如 8=2+4+2, 则在总和为 4 的回文串的基础之上, 可以在两端加上 2 组成一个新的总和为 8 的回文串, 这种情况的种数就是和为 4 并且最小数大于 2 的回文串的种数.
下午脑子不太清楚, 晕了很长时间, 一开始还以为是拆分成两边各一个, 后来突然发现 -- 我踏马在写啥...... 重写了两三次, 没理解清晰题意
B: 滑雪
描述 Michael 喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激. 可是为了获得速度, 滑的区域必须向下倾斜, 而且当你滑到坡底, 你不得不再次走上坡或者等待升降机来载你. Michael 想知道载一个区域中最长的滑坡. 区域由一个二维数组给出. 数组的每个数字代表点的高度. 下面是一个例子
- 1 2 3 4 5
- 16 17 18 19 6
- 15 24 25 20 7
- 14 23 22 21 8
- 13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一, 当且仅当高度减小. 在上面的例子中, 一条可滑行的滑坡为 24-17-16-1. 当然 25-24-23-...-3-2-1 更长. 事实上, 这是最长的一条. 输入输入的第一行表示区域的行数 R 和列数 C(1 <= R,C <= 100). 下面是 R 行, 每行有 C 个整数, 代表高度 h,0<=h<=10000. 输出输出最长区域的长度. 样例输入
- 5 5
- 1 2 3 4 5
- 16 17 18 19 6
- 15 24 25 20 7
- 14 23 22 21 8
- 13 12 11 10 9
样例输出
25
来源
Don't know
- #include <iostream>
- #include <cstdio>
- #include <string.h>
- #include <algorithm>
- #include <stdlib.h>
- #include <math.h>
- using namespace std;
- const int maxn = 105;
- int r, c, sum=1, maxlen=1;
- int dp[maxn][maxn],area[maxn][maxn];
- int dirr[4] = { 0,0,-1,1 }, dirl[4] = { -1,1,0,0 };
- struct node {
- int x, y;
- int high;
- }map[maxn*maxn];
- bool cmp(node&a1,node&a2){
- return a1.high<a2.high;
- }
- void init() {
- scanf("%d%d", &r, &c);
- for (int i = 1; i <= r; i++)
- for (int j = 1; j <= c; j++)
- {
- scanf("%d", &map[sum].high);
- map[sum].x=i,map[sum].y=j;
- area[i][j]=map[sum].high;
- dp[i][j]=1;
- sum++;
- }
- sum--;
- sort(map+1,map+r*c+1,cmp);
- }
- void dpsolve(){
- for(int i=0;i<sum;i++)
- for(int j=0;j<=3;j++)
- {
- if(area[map[i].x+dirr[j]][map[i].y+dirl[j]]>area[map[i].x][map[i].y])
- {
- dp[map[i].x+dirr[j]][map[i].y+dirl[j]]=max(dp[map[i].x+dirr[j]][map[i].y+dirl[j]],dp[map[i].x][map[i].y]+1);
- maxlen=max(maxlen,dp[map[i].x+dirr[j]][map[i].y+dirl[j]]);
- }
- }
- printf("%d",maxlen);
- }
- int main()
- {
- init();
- dpsolve();
- return 0;
- }
- View Code
熟悉的题目...... 把顺治换成了 Michael
解题思路:
将点按高度从小到大排好 (我是从小到大划路线的), 然后看四周有没有点比它高, 高的话就把那个点的 dp 状态加一 ( dp[x][y] 指这个点出发的最长路径)
C: 硬币
描述
宇航员 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, 第二行输出空行.
- #include <iostream>
- #include <cstdio>
- #include <string.h>
- #include <algorithm>
- #include <stdlib.h>
- #include <math.h>
- #include <queue>
- using namespace std;
- const int maxn1 = 205,maxn2=10005;
- int dp[maxn2],coin[maxn1],f[maxn2];
- int n,x,sum;
- queue<int> res;
- void print() {
- int p = res.front();
- printf("%d", coin[p]);
- res.pop();
- while (res.empty() != 1) {
- int p = res.front();
- printf("%d", coin[p]);
- res.pop();
- }
- printf("\n");
- }
- void dpsolve() {
- for(int i=1;i<=n;i++)
- for (int j = x; j>= coin[i]; j--) {
- dp[j] += dp[j - coin[i]];
- }
- for (int i = 1; i <= n; i++)
- {
- memset(f, 0, sizeof(f));
- f[0] = 1;
- for (int j = 1; j <= x; j++)
- {
- if (coin[i]> j)
- f[j] = dp[j];
- else
- f[j] = dp[j] - f[j - coin[i]];
- }
- if (f[x] == 0) {
- sum++;
- res.push(i);
- }
- }
- printf("%d\n", sum);
- if (sum)
- print();
- else
- printf("\n");
- }
- void init() {
- cin>> n>> x;
- int c = n,_c=1;
- while (c--)
- cin>> coin[_c++];
- sort(coin + 1, coin + n + 1);
- dp[0] = 1;
- }
- int main()
- {
- init();
- dpsolve();
- return 0;
- }
- View Code
我为啥数组又开小了...... 浑然不知地 RE 了三次
解题思路:
01 背包算到达某价钱 x 时的总方案数 dp[x]
然后用方程 f[y]=dp[y]-f[y-coin[x]] 算出不用某硬币 x 时凑成 y 时的种数 (虽然 x 不同, 但我在每个循环里都是用的 f[y] )
f[y] 为 0 就表示不能不用它~
D: 最佳加法表达式
描述
给定 n 个 1 到 9 的数字, 要求在数字之间摆放 m 个加号 (加号两边必须有数字), 使得所得到的加法表达式的值最小, 并输出该值. 例如, 在 1234 中摆放 1 个加号, 最好的摆法就是 12+34, 和为 36
输入有不超过 15 组数据
每组数据两行. 第一行是整数 m, 表示有 m 个加号要放 ( 0<=m<=50)
第二行是若干个数字. 数字总数 n 不超过 50, 且 m <= n-1 输出对每组数据, 输出最小加法表达式的值样例输入
- 2
- 123456
- 1
- 123456
- 4
- 12345
样例输出
102 579 15
提示
要用到高精度计算, 即用数组来存放 long long 都装不下的大整数, 并用模拟列竖式的办法进行大整数的加法.
来源
Guo Wei
- #include <iostream>
- #include <cstdio>
- #include <string.h>
- #include <algorithm>
- #include <stdlib.h>
- #include <math.h>
- #include <queue>
- using namespace std;
- const int maxn = 60;
- int m,countnum=0;//countnum 为数字的位数
- char num[maxn];
- class bignum {
- public:
- int longnum[maxn];
- int revs[maxn];
- int len;
- bignum(){
- memset(longnum, 0, sizeof(longnum));
- memset(revs, 0, sizeof(longnum));
- len = 50;
- }
- bignum(char*a) {
- memset(longnum, 0, sizeof(longnum));
- memset(revs, 0, sizeof(longnum));
- for (int i = 0; a[i] != '\0'; i++)
- longnum[i] = a[i] - '0';
- len = strlen(a);
- for (int i = 0; i <len; i++)
- revs[i] = longnum[len-1 - i];
- }
- bignum(char*a, char*b) {
- memset(longnum, 0, sizeof(longnum));
- memset(revs, 0, sizeof(longnum));
- for (int i = 0; i <= b - a; i++)
- longnum[i] = *(a + i) - '0';
- len = b - a + 1;
- for (int i = 0; i < len; i++)
- revs[i] = longnum[len-1 - i];
- }
- bignum operator+(bignum x) {
- int res[maxn] = { 0 }; char _res[maxn]; int lenres;
- for (int i = 0; i < len || i < x.len; i++) {
- res[i] += revs[i] + x.revs[i];
- lenres = i;
- while (res[i]> 9) {
- res[i] -= 10;
- res[i + 1]++;
- lenres = i + 1;
- }
- }
- for (int i = 0; i <= lenres; i++)
- _res[i] = res[lenres - i]+'0';
- return bignum(_res, _res + lenres);
- }
- bool operator<(bignum&x) {
- if (len <x.len)return true;
- if (len> x.len)return false;
- for (int i = 0; i <len; i++)
- {
- if (longnum[i]> x.longnum[i])
- return false;
- else if(longnum[i] <x.longnum[i]) return true;
- }
- return true;
- }
- };
- bignum dp[maxn][maxn];//dp[x][y] 为前 y 个数字里有 x 个加号
- bignum _num;
- void clear() {
- for (int i = 0; i <= m; i++)
- for (int j = 1; j <= countnum; j++)
- dp[i][j] = bignum();
- }
- void dpsolve() {
- for(int i=1;i<=m;i++)
- for (int j = i + 1; j <= countnum; j++) {
- for (int k = i; k < j; k++) {
- bignum res = dp[i - 1][k] + bignum(num + k, num+j - 1);
- if (res < dp[i][j])
- dp[i][j] = res;
- }
- }
- }
- void init() {
- while (cin>> m) {
- cin>> num;
- countnum = strlen(num);
- clear();
- _num = bignum(num);
- for (int i = 1; i <= countnum; i++)
- dp[0][i] = bignum(num, num + i - 1);
- dpsolve();
- for (int i = 0; i < dp[m][countnum].len; i++)
- printf("%d", dp[m][countnum].longnum[i]);
- printf("\n");
- }
- }
- int main()
- {
- init();
- dpsolve();
- return 0;
- }
- View Code
我怕不是 C++ 学傻了
满脑子 C++.jpg
解题思路:
这个最简单了, 用 dp[x][y] 表示前 y 个数字加号有 x 的时候表达式最小值
我里面有很多浪费计算, 不管了
主要是结合了高精度, 比较麻烦, 很容易错
WA 点: 在每个 case 之间没有清空 dp 数组
来源: http://www.bubuko.com/infodetail-2614828.html