7625:三角形最佳路径问题
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
如下所示的由正整数数字构成的三角形:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。
注意:路径上的每一步只能从一个数走到下一层上和它最近的下边(正下方)的数或者右边(右下方)的数。

输入
第一行为三角形高度100>=h>=1,同时也是最底层边的数字的数目。
从第二行开始,每行为三角形相应行的数字,中间用空格分隔。
输出
最佳路径的长度数值。
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

1
8
样例输出
30

8
#include <iostream>

using namespace std;

int A[105][105];
int dp[105][105];

int main()
{
int h;
cin>>h;
for(int i=1;i<=h;i++)
{
for(int j=1;j<=i;j++)
{
cin>>A[i][j];
dp[i][j] = A[i][j];
}
}
for(int i=h-1;i>=1;i--)
{
for(int j=0;j<=i;j++)
{
dp[i][j] = dp[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
}
}
cout<<dp[1][1];

return 0;
}

1759:最长上升子序列
查看 提交 统计 提问
总时间限制: 2000ms 内存限制: 65536kB
描述
一个数的序列bi,当b1 < b2 < ... < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN),我们可以得到一些上升的子序列(ai1, ai2, ..., aiK),这里1 <= i1 < i2 < ... < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8).

你的任务,就是对于给定的序列,求出最长上升子序列的长度。
输入
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000。
输出
最长上升子序列的长度。
样例输入
7
1 7 3 5 9 4 8
样例输出
4
#include <iostream>

using namespace std;

int A[1005];
int dp[1005];

int main()
{
int N, Max=0;
cin>>N;
for(int i=0;i<N;i++)
{
cin>>A[i];
dp[i]=1;
}
for(int i=0;i<N;i++)
{
for(int j=0;j<i;j++)
{
if(A[i]>A[j])
dp[i] = max(dp[j]+1, dp[i]);
}
if(dp[i]>Max)
Max = dp[i];
}
cout<<Max;

return 0;
}

2000:最长公共子上升序列
查看 提交 统计 提问
总时间限制: 10000ms 内存限制: 65536kB
描述
给定两个整数序列,写一个程序求它们的最长上升公共子序列。
当以下条件满足的时候,我们将长度为N的序列S1 , S2 , . . . , SN 称为长度为M的序列A1 , A2 , . . . , AM 的上升子序列:

存在 1 <= i1 < i2 < . . . < iN <= M ,使得对所有 1 <= j <=N,均有Sj = Aij,且对于所有的1 <= j < N,均有Sj < Sj+1。

输入
每个序列用两行表示,第一行是长度M(1 <= M <= 500),第二行是该序列的M个整数Ai (-231 <= Ai < 231 )
输出
在第一行,输出两个序列的最长上升公共子序列的长度L。在第二行,输出该子序列。如果有不止一个符合条件的子序列,则输出任何一个即可。
样例输入
5
1 4 2 5 -12
4
-12 1 2 4
样例输出
2
1 4
/*

最长上升公共子序列
f(i1,i2)表示a1与a2[0..i2],以a1[i1]结尾的最长上升公共子序列
若a2[i2]==a1[i1],
f(i1,i2)=max{ f(i,i2-1) }+1 (0<=i<i1)
若a2[i2]<a1[i1],f(i1,i2)不变
若a2[i2]>a1[i1],f(i1,i2)不变,
max{ f(i,i2) }的值更新
*/
#include <cstdio>
#include <vector>
using namespace std;
const int maxn=510;
int m1,m2,a1[maxn],a2[maxn];
struct node{
int len;
vector<int> iv;
}ans[maxn],cur;
int main(){
scanf("%d",&m1);
for(int i=0;i<m1;i++)
scanf("%d",&a1[i]);
scanf("%d",&m2);
for(int i=0;i<m2;i++)
scanf("%d",&a2[i]);
for(int i=0;i<maxn;i++)
ans[i].len=0;
for(int i2=0;i2<m2;i2++){
cur.len=0; cur.iv.clear();
for(int i1=0;i1<m1;i1++){
if(a2[i2]>a1[i1]&&ans[i1].len>cur.len)
cur=ans[i1];
if(a2[i2]==a1[i1]){
ans[i1]=cur;
ans[i1].len++;
ans[i1].iv.push_back(a1[i1]);
}
}
}
int p=0;
for(int i=1;i<m1;i++){
if(ans[p].len<ans[i].len)
p=i;
}
printf("%d\n",ans[p].len);
if(ans[p].iv.size()){
printf("%d",ans[p].iv[0]);
for(int i=1;i<ans[p].iv.size();i++)
printf(" %d",ans[p].iv[i]);
}
printf("\n");
return 0;
}

参考

参考:最长公共子序列、最长上升子序列、最长公共上升子序列


1775:采药
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
辰辰是个很有潜能、天资聪颖的孩子,他的梦想是称为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”

如果你是辰辰,你能完成这个任务吗?
输入
输入的第一行有两个整数T(1 <= T <= 1000)和M(1 <= M <= 100),T代表总共能够用来采药的时间,M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间(包括1和100)的的整数,分别表示采摘某株草药的时间和这株草药的价值。
输出
输出只包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。
#include <iostream>

using namespace std;

int tim[1005], value[1005], dp[1005];

int T, M, Max=0;


int main()
{
cin>>T>>M;
for(int i=1;i<=M;i++)
{
cin>>tim[i]>>value[i];
}
for(int i=1;i<=M;i++)
{
for(int j=T;j>=tim[i];j--)
{
dp[j] = max(dp[j], dp[j-tim[i]]+value[i]);
}
}
cout<<dp[T];
return 0;
}

6262:流感传染
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
有一批易感人群住在网格状的宿舍区内,宿舍区为n*n的矩阵,每个格点为一个房间,房间里可能住人,也可能空着。在第一天,有些房间里的人得了流感,以后每天,得流感的人会使其邻居传染上流感,(已经得病的不变),空房间不会传染。请输出第m天得流感的人数。

输入
第一行一个数字n,n不超过100,表示有n*n的宿舍房间。
接下来的n行,每行n个字符,’.’表示第一天该房间住着健康的人,’#’表示该房间空着,’@’表示第一天该房间住着得流感的人。
接下来的一行是一个整数m,m不超过100.
输出
输出第m天,得流感的人数
 #include<iostream>
#include<stdio.h>
using namespace std;

int main()
{
char a[101][101];
int n, m, sum = 0;
cin >> n;
for(int i = 0;i < n; i++)
{
for(int j = 0; j < n; j++)
{
cin >> a[i][j];
}
}
cin >> m;
for(int d = 1; d <= m; d++)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n;j++)
{
if(a[i][j] == '!')
a[i][j] = '@'; // 将前一天标记的人感染
}
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n;j++)
{
// 将感染人周围的人标记
if(a[i][j] == '@')
{
if(i + 1 <n && a[i + 1][j] == '.')
a[i + 1][j]='!';
if(j - 1 >= 0 && a[i][j - 1] == '.')
a[i][j - 1] = '!';
if(j + 1 < n && a[i][j + 1] == '.')
a[i][j + 1]='!';
if(i - 1 >= 0 && a[i - 1][j] == '.')
a[i - 1][j] = '!';
}
}
}

}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(a[i][j] == '@')
sum++;
}
}
cout << sum << endl;
return 0;
}

1808:公共子序列
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
我们称序列Z = < z1, z2, ..., zk >是序列X = < x1, x2, ..., xm >的子序列当且仅当存在 严格上升 的序列< i1, i2, ..., ik >,使得对j = 1, 2, ... ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b, c, f, b, c >的子序列。

现在给出两个序列X和Y,你的任务是找到X和Y的最大公共子序列,也就是说要找到一个最长的序列Z,使得Z既是X的子序列也是Y的子序列。
输入
输入包括多组测试数据。每组数据包括一行,给出两个长度不超过200的字符串,表示两个序列。两个字符串之间由若干个空格隔开。
输出
对每组输入数据,输出一行,给出两个序列的最大公共子序列的长度。
样例输入
abcfbc abfcab
programming contest
abcd mnp
样例输出
4
2
0
#include <bits/stdc++.h>

using namespace std;

char A[205], B[205];
int dp[205][205];

int main()
{
while(scanf("%s %s", (A+1), (B+1))!=EOF)
{
int lenA = strlen(A+1);
int lenB = strlen(B+1);
memset(dp, 0, 205*205*sizeof(int));
for(int i=1;i<=lenA;i++)
{
for(int j=1;j<=lenB;j++)
{
if(A[i]==B[j])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
cout<<dp[lenA][lenB]<<endl;
}

return 0;
}

1944:吃糖果
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
名名的妈妈从外地出差回来,带了一盒好吃又精美的巧克力给名名(盒内共有 N 块巧克力,20 > N >0)。妈妈告诉名名每天可以吃一块或者两块巧克力。假设名名每天都吃巧克力,问名名共有多少种不同的吃完巧克力的方案。例如:如果N=1,则名名第1天就吃掉它,共有1种方案;如果N=2,则名名可以第1天吃1块,第2天吃1块,也可以第1天吃2块,共有2种方案;如果N=3,则名名第1天可以吃1块,剩2块,也可以第1天吃2块剩1块,所以名名共有2+1=3种方案;如果N=4,则名名可以第1天吃1块,剩3块,也可以第1天吃2块,剩2块,共有3+2=5种方案。现在给定N,请你写程序求出名名吃巧克力的方案数目。
输入
输入只有1行,即整数N。
输出
输出只有1行,即名名吃巧克力的方案数。
样例输入
4
样例输出
5

这种题目如果实在不会就自己手动推导,找规律

本题实质是斐波那契数列

#include <iostream>

using namespace std;

int N;

int work(int remain)
{
if(remain==1)
return 1;
if(remain==2)
return 2;
return work(remain-1) + work(remain-2);
}

int main()
{
cin>>N;
cout<<work(N);
return 0;
}

dp的方式:

#include <iostream>

using namespace std;

int N;

int dp[25];

int main()
{
cin>>N;
dp[1]=1;
dp[2]=2;
for(int i=3;i<=N;i++)
dp[i] = dp[i-1] + dp[i-2];
cout<<dp[N];

return 0;
}

1996:登山
查看 提交 统计 提问
总时间限制: 5000ms 内存限制: 131072kB
描述
五一到了,PKU-ACM队组织大家去登山观光,队员们发现山上一个有N个景点,并且决定按照顺序来浏览这些景点,即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯,就是不连续浏览海拔相同的两个景点,并且一旦开始下山,就不再向上走了。队员们希望在满足上面条件的同时,尽可能多的浏览景点,你能帮他们找出最多可能浏览的景点数么?

输入
Line 1: N (2 <= N <= 1000) 景点数
Line 2: N个整数,每个景点的海拔
输出
最多能浏览的景点数
样例输入
8
186 186 150 200 160 130 197 220
样例输出
4
#include<cstdio>
#include<iostream>
using namespace std;
#define N 1005
int n,ans;int a[N],f1[N],f2[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) f1[i]=f2[i]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
if(a[i]>a[j]) f1[i]=max(f1[i],f1[j]+1);
for(int i=n;i>0;i--)
for(int j=n;j>i;j--)
if(a[i]>a[j]) f2[i]=max(f2[i],f2[j]+1);
for(int i=1;i<=n;i++)
ans=max(f1[i]+f2[i]-1,ans);
printf("%d",ans);
}

7627:鸡蛋的硬度
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
最近XX公司举办了一个奇怪的比赛:鸡蛋硬度之王争霸赛。参赛者是来自世 界各地的母鸡,比赛的内容是看谁下的蛋最硬,更奇怪的是XX公司并不使用什么精密仪器来测量蛋的硬度,他们采用了一种最老土的办法--从高度扔鸡蛋--来 测试鸡蛋的硬度,如果一次母鸡下的蛋从高楼的第a层摔下来没摔破,但是从a+1层摔下来时摔破了,那么就说这只母鸡的鸡蛋的硬度是a。你当然可以找出各种 理由说明这种方法不科学,比如同一只母鸡下的蛋硬度可能不一样等等,但是这不影响XX公司的争霸赛,因为他们只是为了吸引大家的眼球,一个个鸡蛋从100 层的高楼上掉下来的时候,这情景还是能吸引很多人驻足观看的,当然,XX公司也绝不会忘记在高楼上挂一条幅,写上“XX公司”的字样--这比赛不过是XX 公司的一个另类广告而已。
勤于思考的小A总是能从一件事情中发现一个数学问题,这件事也不例外。“假如有很多同样硬度的鸡蛋,那么我可以用二分的办法用最少的次数测出鸡蛋 的硬度”,小A对自己的这个结论感到很满意,不过很快麻烦来了,“但是,假如我的鸡蛋不够用呢,比如我只有1个鸡蛋,那么我就不得不从第1层楼开始一层一 层的扔,最坏情况下我要扔100次。如果有2个鸡蛋,那么就从2层楼开始的地方扔……等等,不对,好像应该从1/3的地方开始扔才对,嗯,好像也不一定 啊……3个鸡蛋怎么办,4个,5个,更多呢……”,和往常一样,小A又陷入了一个思维僵局,与其说他是勤于思考,不如说他是喜欢自找麻烦。
好吧,既然麻烦来了,就得有人去解决,小A的麻烦就靠你来解决了:)

输入
输入包括多组数据,每组数据一行,包含两个正整数n和m(1<=n<=100,1<=m<=10),其中n表示楼的高度,m表示你现在拥有的鸡蛋个数,这些鸡蛋硬度相同(即它们从同样高的地方掉下来要么都摔碎要么都不碎),并且小于等于n。你可以假定硬度为x的鸡蛋从高度小于等于x的地方摔无论如何都不会碎(没摔碎的鸡蛋可以继续使用),而只要从比x高的地方扔必然会碎。
对每组输入数据,你可以假定鸡蛋的硬度在0至n之间,即在n+1层扔鸡蛋一定会碎。
输出
对于每一组输入,输出一个整数,表示使用最优策略在最坏情况下所需要的扔鸡蛋次数。
样例输入
100 1
100 2
样例输出
100
14
提示
最优策略指在最坏情况下所需要的扔鸡蛋次数最少的策略。
如果只有一个鸡蛋,你只能从第一层开始扔,在最坏的情况下,鸡蛋的硬度是100,所以需要扔100次。如果采用其他策略,你可能无法测出鸡蛋的硬度(比如你第一次在第二层的地方扔,结果碎了,这时你不能确定硬度是0还是1),即在最坏情况下你需要扔无限次,所以第一组数据的答案是100。
来源

参考

用dp,首先我们先看样例2(因为样例1谁都会)。为什么是14呢?那我们设丢x次, 
如果x次碎了。那么就在1~x-1次试。否则我们就在x+x-1次试。最后我可以知道答案就是x(x+1)/2<=100。求出来就是14了。
那么不是两个鸡蛋呢我们就试着枚举第x层。如果鸡蛋碎了那么我们就找下面一层,同时鸡蛋数-1。如果没碎那么就找n-x~x+1的位置。
然后帅气的dp方程就出来了f[i][j]=max(f[i-1][j-1],f[n-i][j])+1!!!
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[110][11];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j]=i;
}
}
for(int i=1;i<=n;i++)
{
for(int k=1;k<=i;k++)//枚举
{
for(int j=2;j<=m;j++)
{
f[i][j]=min(f[i][j],max(f[k-1][j-1],f[i-k][j])+1);//dp
}
}
}
printf("%d\n",f[n][m]);
}
return 0;
}

1768:最大子矩阵
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。

比如,如下4 * 4的矩阵

0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

的最大子矩阵是

9 2
-4 1
-1 8

这个子矩阵的大小是15。
输入
输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。再后面的若干行中,依次(首先从左到右给出第一行的N个整数,再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数,整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[-127, 127]。
输出
输出最大子矩阵的大小。
样例输入
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1

8 0 -2
样例输出
15

参考

看不懂啊。。。。
#include <stdio.h>
const int SIZE = 100;
int matrix[SIZE + 1][SIZE + 1];
int rowsum[SIZE + 1][SIZE + 1]; //rowsum[i][j]记录第 i 行前 j 个数的和
int m, n, i, j, first, last, area, ans;
int main()
{
scanf("%d",&n);
m=n;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
scanf("%d", &matrix[i][j]);
ans = matrix[1][1];
for (i = 1; i <= m; i++)
rowsum[i][0]=0;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
rowsum[i][j] = rowsum[i][j-1]+matrix[i][j];
for (first = 1; first <= n; first++)
for (last = first; last <= n; last++)
{
area=0;
for (i = 1; i <= m; i++)
{
area += rowsum[i][last] -rowsum[i][first-1];
if (area > ans) ans = area;
if (area < 0) area = 0;
}
}
printf("%d\n", ans);
return 0;
}

原题

2728:摘花生
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
Hello Kitty 想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。Hello Kitty只能向东或向南走,不能向西或向北走。问Hello Kitty 最多能够摘到多少颗花生。

输入
第一行是一个整数T,代表一共有多少组数据。1<=T <= 100
接下来是T组数据。

每组数据的第一行是两个整数,分别代表花生苗的行数R和列数 C ( 1<= R,C <=100)
每组数据的接下来R行数据,从北向南依次描述每行花生苗的情况。每行数据有 C 个整数,按从西向东的顺序描述了该行每株花生苗上的花生数目 M ( 0<= M <= 1000)。
输出
对每组输入数据,输出一行,内容为Hello Kitty能摘到得最多的花生颗数。
样例输入
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
样例输出
8
16
#include <iostream>

using namespace std;

const int maxn=105;
int A[maxn][maxn];
int B[maxn][maxn];

int main()
{
int T;
cin>>T;
while(T--)
{
int R, C;
cin>>R>>C;
for(int i=1;i<=R;i++)
{
for(int j=1;j<=C;j++)
{
cin>>A[i][j];
B[i][j]=A[i][j];
}
}
for(int j=2;j<=C;j++)
B[1][j] = B[1][j]+B[1][j-1];
for(int i=2;i<=R;i++)
B[i][1] = B[i][1]+B[i-1][1];
for(int i=2;i<=R;i++)
{
for(int j=2;j<=C;j++)
{
B[i][j] = max(B[i-1][j], B[i][j-1])+B[i][j];
}
}
cout<<B[R][C]<<endl;
}

return 0;
}
#include <bits/stdc++.h>

using namespace std;
const int maxn=105;
int dp[maxn][maxn], A[maxn][maxn];

int main()
{
int T;
cin>>T;
while(T--)
{
int R, C;
cin>>R>>C;
memset(dp, 0, sizeof(dp));
memset(A, 0, sizeof(A));
for(int i=1;i<=R;i++)
{
for(int j=1;j<=C;j++)
{
cin>>A[i][j];
}
}
dp[1][1]=A[1][1];
for(int i=1;i<=R;i++)
{
for(int j=1;j<=C;j++)
{
dp[i][j]=max(dp[i-1][j], dp[i][j-1])+A[i][j];
}
}
cout<<dp[R][C]<<endl;

}
return 0;
}

2718:移动路线
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
×桌子上有一个m行n列的方格矩阵,将每个方格用坐标表示,行坐标从下到上依次递增,列坐标从左至右依次递增,左下角方格的坐标为(1,1),则右上角方格的坐标为(m,n)。
小明是个调皮的孩子,一天他捉来一只蚂蚁,不小心把蚂蚁的右脚弄伤了,于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中,蚂蚁从
左下角的方格中移动到右上角的方格中,每步移动一个方格。蚂蚁始终在方格矩阵内移动,请计算出不同的移动路线的数目。
对于1行1列的方格矩阵,蚂蚁原地移动,移动路线数为1;对于1行2列(或2行1列)的方格矩阵,蚂蚁只需一次向右(或向上)移动,移动路线数也为1……对于一个2行3列的方格矩阵,如下图所示:

-------------------
|(2,1)|(2,2)|(2,3)|
-------------------
|(1,1)|(1,2)|(1,3)|
-------------------

蚂蚁共有3种移动路线:
路线1:(1,1) → (1,2) → (1,3) → (2,3)
路线2:(1,1) → (1,2) → (2,2) → (2,3)
路线3:(1,1) → (2,1) → (2,2) → (2,3)
输入
输入只有一行,包括两个整数m和n(0<m+n<=20),代表方格矩阵的行数和列数,m、n之间用空格隔开
输出
输出只有一行,为不同的移动路线的数目。
样例输入
2 3
样例输出
3
#include <iostream>

using namespace std;

int A[20][20];
int m, n, cnt;

void dfs(int i, int j)
{
if(i==m&&j==n)
{
cnt++;
}
if(i>m||j>n)
return;
dfs(i+1,j);
dfs(i,j+1);

}

int main()
{

cin>>m>>n;
cnt=0;
dfs(1,1);
cout<<cnt;


return 0;
}

另一种方法:

这道题同样是找规律,根据下图我们可以发现(2,2)的路线数目等于(1,2)与(2,1)路线数目之后,而且其它也是类似的,可以找到规律是a[i][j]=a[i-1][j]+a[i] 

递推,某一个点只能从其左边或者下边走过来
f[i][j]存储(i,j)这个点上的结果,即f[i][j]=f[i-1][j]+f[i][j-1]
#include<bits/stdc++.h>
using namespace std;
int n,m,a[21][21],i,j;
int main()
{
cin>>m>>n;
a[1][1]=1;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
a[i][j]+=a[i-1][j]+a[i][j-1];
cout<<a[m][n]<<endl;
return 0;

}

2985:数字组合
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
有n个正整数,找出其中和为t(t也是正整数)的可能的组合方式。如:
n=5,5个数分别为1,2,3,4,5,t=5;
那么可能的组合有5=1+4和5=2+3和5=5三种组合方式。
输入
输入的第一行是两个正整数n和t,用空格隔开,其中1<=n<=20,表示正整数的个数,t为要求的和(1<=t<=1000)
接下来的一行是n个正整数,用空格隔开。
输出
和为t的不同的组合方式的数目。
样例输入
5 5
1 2 3 4 5
样例输出
3
#include <bits/stdc++.h>

using namespace std;

int A[25];
int n, t;
int cnt;

void dfs(int index, int sum)
{
if(sum==t)
{
cnt++;
return;
}
if(sum>t||index==n)
return;

dfs(index+1,sum);
dfs(index+1, sum+A[index]);

}

int main()
{

cin>>n>>t;
cnt=0;
for(int i=0;i<n;i++)
cin>>A[i];
sort(A, A+n);
dfs(0, 0);
cout<<cnt;


return 0;
}

01背包

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,t;
int a[1005],f[1005];
int main(){//01背包
scanf("%d%d",&n,&t);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=t;j>=a[i];j--)
f[j]+=f[j-a[i]];
printf("%d\n",f[t]);
return 0;
}

2988:计算字符串距离
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
对于两个不同的字符串,我们有一套操作方法来把他们变得相同,具体方法为:
修改一个字符(如把“a”替换为“b”)
删除一个字符(如把“traveling”变为“travelng”)

比如对于“abcdefg”和“abcdef”两个字符串来说,我们认为可以通过增加/减少一个“g”的方式来达到目的。无论增加还是减少“g”,我们都仅仅需要一次操作。我们把这个操作所需要的次数定义为两个字符串的距离。
给定任意两个字符串,写出一个算法来计算出他们的距离。
输入
第一行有一个整数n。表示测试数据的组数,
接下来共n行,每行两个字符串,用空格隔开。表示要计算距离的两个字符串
字符串长度不超过1000。
输出
针对每一组测试数据输出一个整数,值为两个字符串的距离。
样例输入
3
abcdefg abcdef
ab ab
mnklj jlknm
样例输出
1
0
4
分析:

类似最长公共子序列,逐个比较两字符串内各个字符。

定义f[i][j]为a中前i个,b中前j个字符的最小距离(题目显然是要求最小的距离)。

如果相同,则不需修改任何东西,距离相当于这两个字符之前的字符串的距离;

如果不同,有三种修改方式:

  1.删除a串中当前第i个字符,距离为a串前i - 1个字符与b串前j个字符的距离再加修改一个字符的距离1;

  2.删除b串中当前第j个字符,距离为b串前j - 1个字符与a串前i个字符的距离再加修改一个字符的距离1;

  3.将a串第i个字符修改为b串第j个字符,变成相同的,与相同时转移方程相同,再加1;

f[i][j] = (f[i - 1][j - 1]), (a[i] == b[j]) ||

  ( min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1 ), (a[i] != b[j])

但是!当不同时应先选择三种方式中距离最小的,最后再加一,这应该容易理解
#include<iostream>
#include<string.h>
using namespace std;
//http://noi.openjudge.cn/ch0206/2988/
//3种操作,a字符串删除一个,b字符串删除一个,直接改变字符
//关键是要对dp数组的第0行和第0列初始赋值
int n,len1,len2,dp[1100][1100];
char a[1100],b[1100];
void f(){
for(int i=0;i<=len1;i++)dp[i][0]=i;//开始只循环到len-1,错了
for(int i=0;i<=len2;i++)dp[0][i]=i;
for(int i=0;i<len1;i++){
for(int j=0;j<len2;j++){
if(a[i]==b[j]){
dp[i+1][j+1]=dp[i][j];
}
else{
dp[i+1][j+1]=min(min(dp[i+1][j],dp[i][j+1]),dp[i][j])+1;
}
//cout<<i+1<<" "<<j+1<<" "<<dp[i+1][j+1]<<endl;
}
}
cout<<dp[len1][len2]<<endl;
}
int main(){
cin>>n;
while(n--){
cin>>a>>b;
len1=strlen(a);
len2=strlen(b);
f();
}
}

2989:糖果
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
由于在维护世界和平的事务中做出巨大贡献,Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。在这一天,Dzx可以从糖果公司的N件产品中任意选择若干件带回家享用。糖果公司的N件产品每件都包含数量不同的糖果。Dzx希望他选择的产品包含的糖果总数是K的整数倍,这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。当然,在满足这一条件的基础上,糖果总数越多越好。Dzx最多能带走多少糖果呢?
注意:Dzx只能将糖果公司的产品整件带走。
输入
第一行包含两个整数N(1<=N<=100)和K(1<=K<=100)
以下N行每行1个整数,表示糖果公司该件产品中包含的糖果数目,不超过1000000
输出
符合要求的最多能达到的糖果总数,如果不能达到K的倍数这一要求,输出0
样例输入
5 7
1
2
3
4
5
样例输出
14
提示
Dzx的选择是2+3+4+5=14,这样糖果总数是7的倍数,并且是总数最多的选择。
正统做法是背包DP,不过若是直接套也不行,这里的糖果总数太多,时间和空间都不够用。所以在这里设f(i,j)=前i个糖果选一些构成j%k的最大值,函数里的j是mod k过的,这样优化后情况就会好很多。
方程为f(i,j)=max(f(i-1,j), f(i-1,(j-a[i]%k+k)%k)+a[i] ); 边界为d[i][0]=0。答案即为d[n][0]。
需要注意f(i,j)不能初始化为0
#include <bits/stdc++.h>

using namespace std;

int N, K;
int A[105];
int dp[105][105];

int main()
{
cin>>N>>K;
for(int i=1;i<=N;i++)
{
cin>>A[i];
}
memset(dp, -20, sizeof(dp));//必须,-1会出错,背包九讲,恰好装满背包除了F[0]外,其它F[1--V]均设为-INF
for(int i=0;i<=N;i++)
dp[i][0]=0;
for(int i=1;i<=N;i++)
{
for(int j=0;j<K;j++)
{
dp[i][j]=max(dp[i-1][j], dp[i-1][(j-A[i]%K+K)%K]+A[i]);
}
}
cout<<dp[N][0];


return 0;
}

3531:判断整除
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
一个给定的正整数序列,在每个数之前都插入+号或-号后计算它们的和。比如序列:1、2、4共有8种可能的序列:
(+1) + (+2) + (+4) = 7
(+1) + (+2) + (-4) = -1
(+1) + (-2) + (+4) = 3
(+1) + (-2) + (-4) = -5
(-1) + (+2) + (+4) = 5
(-1) + (+2) + (-4) = -3
(-1) + (-2) + (+4) = 1
(-1) + (-2) + (-4) = -7
所有结果中至少有一个可被整数k整除,我们则称此正整数序列可被k整除。例如上述序列可以被3、5、7整除,而不能被2、4、6、8……整除。注意:0、-3、-6、-9……都可以认为是3的倍数。

输入
输入的第一行包含两个数:N(2 < N < 10000)和k(2 < k< 100),其中N代表一共有N个数,k代表被除数。第二行给出序列中的N个整数,这些整数的取值范围都0到10000之间(可能重复)。
输出
如果此正整数序列可被k整除,则输出YES,否则输出NO。(注意:都是大写字母)
样例输入
3 2
1 2 4
样例输出
NO
(a%k+b%k)%k=(a+b)%k

参考

#include<iostream>
using namespace std;
int main()
{
int a[10001] = { 0 }, n, k;
bool f[10001][101] = { 0 };//每个i得到的余数可能有正负两个值,用bool型 ;f[i][j]表示用前i个数计算能得到余数j
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] %= k;
}
f[1][a[1]] = true;
for (int i = 2; i <= n; i++)
for (int j = 0; j < k; j++)
if (f[i - 1][j])
{
f[i][(j + a[i]) % k] = true;
f[i][(j - a[i] + k) % k] = true;
}//第一个%k避免下标出现负数 加法与%的交换律
if (f[n][0])
cout << "YES";
else
cout << "NO";
return 0;
}

3532:最大上升子序列和
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
一个数的序列bi,当b1 < b2 < ... < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, ...,aN),我们可以得到一些上升的子序列(ai1, ai2, ..., aiK),这里1 <= i1 < i2 < ... < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中序列和最大为18,为子序列(1, 3, 5, 9)的和.

你的任务,就是对于给定的序列,求出最大上升子序列和。注意,最长的上升子序列的和不一定是最大的,比如序列(100, 1, 2, 3)的最大上升子序列和为100,而最长上升子序列为(1, 2, 3)

输入
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000(可能重复)。
输出
最大上升子序列和
样例输入
7
1 7 3 5 9 4 8
样例输出
18
#include <iostream>

using namespace std;

int A[1005];
int dp[1005];

int main()
{
int N, Max=0;
cin>>N;
for(int i=1;i<=N;i++)
{
cin>>A[i];
dp[i]=A[i];
}
for(int i=1;i<=N;i++)
{
for(int j=1;j<i;j++)
{
if(A[i]>A[j])
dp[i]=max(dp[i], dp[j]+A[i]);
}
if(dp[i]>Max)
Max=dp[i];
}
cout<<Max;


return 0;
}

4978:宠物小精灵之收服
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。



一天,小智和皮卡丘来到了小精灵狩猎场,里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而,野生的小精灵并不那么容易被收服。对于每一个野生小精灵而言,小智可能需要使用很多个精灵球才能收服它,而在收服过程中,野生小精灵也会对皮卡丘造成一定的伤害(从而减少皮卡丘的体力)。当皮卡丘的体力小于等于0时,小智就必须结束狩猎(因为他需要给皮卡丘疗伤),而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。当小智的精灵球用完时,狩猎也宣告结束。

我们假设小智遇到野生小精灵时有两个选择:收服它,或者离开它。如果小智选择了收服,那么一定会扔出能够收服该小精灵的精灵球,而皮卡丘也一定会受到相应的伤害;如果选择离开它,那么小智不会损失精灵球,皮卡丘也不会损失体力。

小智的目标有两个:主要目标是收服尽可能多的野生小精灵;如果可以收服的小精灵数量一样,小智希望皮卡丘受到的伤害越小(剩余体力越大),因为他们还要继续冒险。

现在已知小智的精灵球数量和皮卡丘的初始体力,已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。请问,小智该如何选择收服哪些小精灵以达到他的目标呢?

输入
输入数据的第一行包含三个整数:N(0 < N < 1000),M(0 < M < 500),K(0 < K < 100),分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。
之后的K行,每一行代表一个野生小精灵,包括两个整数:收服该小精灵需要的精灵球的数量,以及收服过程中对皮卡丘造成的伤害。
输出
输出为一行,包含两个整数:C,R,分别表示最多收服C个小精灵,以及收服C个小精灵时皮卡丘的剩余体力值最多为R。
样例输入
样例输入1:
10 100 5
7 10
2 40
2 50
1 20
4 20

样例输入2:
10 100 5
8 110
12 10
20 10
5 200
1 110
样例输出
样例输出1:
3 30

样例输出2:
0 100
提示
对于样例输入1:小智选择:(7,10) (2,40) (1,20) 这样小智一共收服了3个小精灵,皮卡丘受到了70点伤害,剩余100-70=30点体力。所以输出3 30
对于样例输入2:小智一个小精灵都没法收服,皮卡丘也不会收到任何伤害,所以输出0 100

二维背包,只不过最后处理体力值有些麻烦,其实只需要看与最大值相等的用体力最少方法即可

找到所剩的体力最大值判断d[N][i]==d[N][M],i是最少消耗的体力值

#include <iostream>

using namespace std;

int A[105];//需要的精灵球的数量
int B[105];//收服过程中对皮卡丘造成的伤害。

int dp[1005][505];//d[i][j]代表:有i个球,j体力,最多能捕获多少精灵
//用了j个精灵球,耗费了k的体力

int main()
{
int N, M, K;
cin>>N>>M>>K;
for(int i=1;i<=K;i++)
cin>>A[i]>>B[i];
for(int i=1;i<=K;i++)
{
for(int j=N;j>=A[i];j--)
{
for(int k=M;k>=B[i];k--)
{
dp[j][k]=max(dp[j][k], dp[j-A[i]][k-B[i]]+1);
}
}
}
cout<<dp[N][M]<<" ";
for(int k=0;k<=M;k++)
{
if(dp[N][k]==dp[N][M])
{
int Min = k;
cout<<M-Min;
return 0;
}
}


return 0;
}

4982:踩方格
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
有一个方格矩阵,矩阵边界在无穷远处。我们做如下假设:
a. 每走一步时,只能从当前方格移动一格,走到某个相邻的方格上;
b. 走过的格子立即塌陷无法再走第二次;
c. 只能向北、东、西三个方向走;
请问:如果允许在方格矩阵上走n步,共有多少种不同的方案。2种走法只要有一步不一样,即被认为是不同的方案。

输入
允许在方格上行走的步数n(n <= 20)
输出
计算出的方案数量
样例输入
2
样例输出
7
//第i步的北方向=上一步北方向数+上一步东西方向数  东西方向=上一步北方向*2+上一步东西方向

//上一步北方向数=上上步方向数和

//所以有 d[i]=d[i-1]+d[i-2]*2+(d[i-1]-d[i-2])


#include <iostream>

using namespace std;

int dp[25];

int main()
{
int n;
cin>>n;
//dp[0]=0;
dp[1]=3;dp[2]=7;
for(int i=3;i<=22;i++)
{
dp[i]=dp[i-1]+dp[i-2]*2 + (dp[i-1]-dp[i-2]);
}
cout<<dp[n];

return 0;
}

6045:开餐馆
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列m1, m2, ... mn 来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用pi 表示在mi 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。



输入
标准的输入包含若干组测试数据。输入第一行是整数T (1 <= T <= 1000) ,表明有T组测试数据。紧接着有T组连续的测试。每组测试数据有3行,
第1行:地点总数 n (n < 100), 距离限制 k (k > 0 && k < 1000).
第2行:n 个地点的位置m1 , m2, ... mn ( 1000000 > mi > 0 且为整数,升序排列)
第3行:n 个地点的餐馆利润p1 , p2, ... pn ( 1000 > pi > 0 且为整数)
输出
对于每组测试数据可能的最大利润
样例输入
2
3 11
1 2 15
10 2 30
3 16
1 2 15
10 2 30
样例输出
40
30

转化成LIS:最长不下降子序列

#include <bits/stdc++.h>

using namespace std;

int A[105], B[105];
int dp[105];

int main()
{
int T;
cin>>T;
while(T--)
{
int n, k, Max=0;
memset(dp, 0, sizeof(dp));
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>A[i];
}
for(int i=1;i<=n;i++)
{
cin>>B[i];
dp[i]=B[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(A[i]-A[j]>k)
dp[i]=max(dp[i],dp[j]+B[i]);
}
Max=max(Max, dp[i]);
}

cout<<Max<<endl;
}

return 0;
}

6046:数据包的调度机制
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
随着 Internet的迅猛发展,多媒体技术和电子商务应用日益广泛,Internet上的服务质量

(QoS,Qualityof Service)问题已越来越受到重视。网络中采用的数据包调度机制与网络的服务质量 QoS 有着密切的关系。研究表明传统的基于队列的调度机制已不能满足网络服务质量QoS 的需求。服务质量 QoS 取决于数据包的延迟。每一个数据包都有一个延迟惩罚值。由于数据包承载的数据不同,不同数据包的延迟惩罚值也可能不同。此外,数据包的延迟也和它的发送顺序有关。如果一个数据包被第K个发送,假设它的延迟惩罚值是D,则这个数据包的最终延迟是 (K - 1) * D。北京大学2012 级信息学院的同学在程序设计课堂上,设计了一种新的基于栈的数据包的调度算法。同学们通过栈的先进后出(Last in First out)的原理,改变数据包的发送顺序,以减小数据包的延迟总值。给定N 个等待调度的数据包,起始这N 个数据包排成一个队列等待发送。接着,这些数据包按序进栈,调度算法可以控制数据包的出栈顺序。因此通过栈,可以将后面的数据包先于前面的数据包发送出去。请你实现一个调度算法使N 个数据包的延迟总值最小。

输入
标准的输入包含若干组测试数据。输入第一行是整数T(1 <= T <= 1000),表明有T组测试数据。紧接着有T组连续的测试。每一组测试数据的第1行是 N(N <= 100),表述数据包的个数。接着的 N 行,每一行是一个整数,第i 行表示数据包i的延迟惩罚值( <=50 )。
输出
对于每组测试数据,输出最小的延迟总值。
样例输入
1
5
5
4
3
2
2
样例输出
24

参考


dp



#include <bits/stdc++.h>

using namespace std;

int A[5]={10, 20, 50, 100};
int dp[1005];

int main()
{
int n;
cin>>n;
dp[0]=1;
if(n%10 != 0||n==0)
{
cout<<0<<endl;
return 0;
}
for(int i=0;i<4;i++)
{
for(int v=A[i];v<=n;v++)
{
dp[v]+=dp[v-A[i]];
}
}
cout<<dp[n]<<endl;
return 0;
}

暴力, 可以AC

#include<bits/stdc++.h>
using namespace std;
int n,s,a,b,c,d;
int main()
{
cin>>n;
if(n==0||n%10!=0)
{

cout<<0<<endl;return 0;
}
for(a=0;a<=n/10;a++)
for( b=0;b<=n/20;b++)
for( c=0;c<=n/50;c++)
for(d=0;d<=n/100;d++)
if(10*a+20*b+50*c+100*d==n)
s++;
cout<<s<<endl;
return 0;

}

7614:最低通行费
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
一个商人穿过一个 N*N 的正方形的网格,去参加一个非常重要的商务活动。他要从网格的左上角进,右下角出。每穿越中间1个小方格,都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时,都需要缴纳一定的费用。

这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用?

注意:不能对角穿越各个小方格(即,只能向上下左右四个方向移动且不能离开网格)。

输入
第一行是一个整数,表示正方形的宽度N (1 <= N < 100);
后面 N 行,每行 N 个不大于 100 的整数,为网格上每个小方格的费用。
输出
至少需要的费用。
样例输入
5
1 4 6 8 10
2 5 7 15 17
6 8 9 18 20
10 11 12 19 21
20 23 25 29 33
样例输出
109

不要被2N-1吓到,分析一下

#include <iostream>

using namespace std;

int A[105][105];
int dp[105][105];

int main()
{
int N;
cin>>N;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
cin>>A[i][j];
dp[i][j]=A[i][j];
}
}
for(int i=2;i<=N;i++)
{
dp[i][1]+=dp[i-1][1];
dp[1][i]+=dp[1][i-1];
}
for(int i=2;i<=N;i++)
{
for(int j=2;j<=N;j++)
{
dp[i][j]=min(dp[i-1][j], dp[i][j-1])+dp[i][j];
}
}
cout<<dp[N][N];

return 0;
}

7624:山区建小学
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
政府在某山区修建了一条道路,恰好穿越总共m个村庄的每个村庄一次,没有回路或交叉,任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di(为正整数),其中,0 < i < m。为了提高山区的文化素质,政府又决定从m个村中选择n个村建小学(设 0 < n < = m < 500 )。请根据给定的m、n以及所有相邻村庄的距离,选择在哪些村庄建小学,才使得所有村到最近小学的距离总和最小,计算最小值。

输入
第1行为m和n,其间用空格间隔
第2行为(m-1) 个整数,依次表示从一端到另一端的相邻村庄的距离,整数之间以空格间隔。

例如
10 3
2 4 6 5 2 4 3 1 3
表示在10个村庄建3所学校。第1个村庄与第2个村庄距离为2,第2个村庄与第3个村庄距离为4,第3个村庄与第4个村庄距离为6,...,第9个村庄到第10个村庄的距离为3。
输出
各村庄到最近学校的距离之和的最小值。
样例输入
10 2
3 1 3 1 1 1 1 1 3
样例输出
18
#include<bits/stdc++.h>
using namespace std;
int n, m, f[500][500], mi[500][500], i, j, a[1001];

/*
思路:明显的动态规划,dp[i][j]表示在前i个村庄中间建立j个小学的花费,
就是在前面(1,k)建立j-1个小学,在(k+1,n)建立1个小学,
他们的花费最小,很显然想求dp[i][j],那么肯定要先求出dp[k][j - 1],典型的动态规划
*/
int main()
{
cin >> n >> m;
int tmp;
a[1]=0;
for(int i=2;i<=n+1;i++)
{
cin>>tmp;
a[i]=a[i-1]+tmp;
}
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
f[i][j] = 9999999;//赋为最大值
for (i = 1; i <= n; i++)
{
for (j = i + 1; j <= n; j++)
mi[i][j] = mi[i][j - 1] + a[j] - a[(i + j) / 2];//从第i个村庄到第j个村庄中只建一个小学的状态转移方程
f[i][1] = mi[1][i];//状态转移方程的边界

}

for (i = 2; i <= n; i++)
for (j = 2; j <= m; j++)
for (int k = j - 1; k < i; k++)
f[i][j] = min(f[i][j], f[k][j - 1] + mi[k + 1][i]);
cout << f[n][m] << endl;

return 0;
}

8462:大盗阿福
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。

这条街上一共有 N 家店铺,每家店中都有一些现金。阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。

作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?

输入
输入的第一行是一个整数 T (T <= 50) ,表示一共有 T 组数据。
接下来的每组数据,第一行是一个整数 N (1 <= N <= 100, 000) ,表示一共有 N 家店铺。第二行是 N 个被空格分开的正整数,表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过 1000 。
输出
对于每组数据,输出一行。该行包含一个整数,表示阿福在不惊动警察的情况下可以得到的现金数量。
样例输入
2
3
1 8 2
4
10 7 6 14
样例输出
8
24

超时代码:

#include <iostream>

using namespace std;

int a[100005];
int dp[100005];

int main()
{
int T;
cin>>T;
while(T--)
{
int N, Max=0;
cin>>N;
for(int i=1;i<=N;i++)
{
cin>>a[i];
dp[i]=a[i];
}
for(int i=1;i<=N;i++)
{
for(int j=1;j<=i-2;j++)
{
dp[i]=max(dp[i], dp[j]+a[i]);
}
Max = max(Max, dp[i]);
}
cout<<Max<<endl;
}
return 0;
}

dp代码:

#include <iostream>

using namespace std;

int a[100005];
int dp[100005];

int main()
{
int T;
cin>>T;
while(T--)
{
int N, Max=0;
cin>>N;
for(int i=1;i<=N;i++)
{
cin>>a[i];
dp[i]=a[i];
}
for(int i=1;i<=N;i++)
{
dp[i]=max(dp[i-1], dp[i-2]+a[i]);
}
cout<<dp[N]<<endl;
}
return 0;
}

分析思路:

f[i] = max(f[i-1], f[i-2]+a[i])

f[i-1]表示不抢这家店,f[i-2]+a[i]表示抢这家店


8464:股票买卖
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
最近越来越多的人都投身股市,阿福也有点心动了。谨记着“股市有风险,入市需谨慎”,阿福决定先来研究一下简化版的股票买卖问题。

假设阿福已经准确预测出了某只股票在未来 N 天的价格,他希望买卖两次,使得获得的利润最高。为了计算简单起见,利润的计算方式为卖出的价格减去买入的价格。

同一天可以进行多次买卖。但是在第一次买入之后,必须要先卖出,然后才可以第二次买入。

现在,阿福想知道他最多可以获得多少利润。

输入
输入的第一行是一个整数 T (T <= 50) ,表示一共有 T 组数据。
接下来的每组数据,第一行是一个整数 N (1 <= N <= 100, 000) ,表示一共有 N 天。第二行是 N 个被空格分开的整数,表示每天该股票的价格。该股票每天的价格的绝对值均不会超过 1,000,000 。
输出
对于每组数据,输出一行。该行包含一个整数,表示阿福能够获得的最大的利润。
样例输入
3
7
5 14 -2 4 9 3 17
6
6 8 7 4 1 -2
4
18 9 5 2
样例输出
28
2
0
#include <bits/stdc++.h>


using namespace std;

const int maxn=100005;
int a[maxn];
int dp1[maxn], dp2[maxn];
int inf=0x3f3f3f3f;

int main()
{
int T, N;
scanf("%d", &T);
while(T--)
{
scanf("%d", &N);
int Max=-inf, Min=inf;
memset(dp1, 0, sizeof(dp1));//必须初始化
memset(dp2, 0, sizeof(dp2));
for(int i=1;i<=N;i++)
{
scanf("%d", &a[i]);
}
for(int i=1;i<=N;i++)
{
Min=min(a[i], Min);
dp1[i]=max(dp1[i-1], a[i]-Min);
}
for(int i=N;i>=1;i--)
{
Max=max(a[i], Max);
dp2[i]=max(dp2[i+1], Max-a[i]);
}
int ans=0;
for(int i=1;i<=N;i++)
{
ans=max(ans, dp1[i]+dp2[i]);
}
printf("%d\n", ans);

}

return 0;
}

注意:在大量数据读写时,必须用scanf,不然会超时,比如本题使用cin会超时。

思路:主要不好想到定义问题状态,一开始想枚举第一次股票交易的卖出时间【这样O(1)处理第一次买入时间,logN处理第二次最大利益(第二次交易实际上是取最大值,所以可以用堆维护)】,但TNlogN就tle了。

正解是dp1(i)代表1-i天一次交易的最大收益;再dp2(i)代表i-n天的最大收益。

以dp1(i) = max( dp1(i-1) , a[i]-prev[i] ),prev是最小前缀,dp2同理。

这样O(n)做完。

类似题UVA 11078 Open Credit System


8467:鸣人的影分身
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
在火影忍者的世界里,令敌人捉摸不透是非常关键的。我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。



影分身是由鸣人身体的查克拉能量制造的,使用的查克拉越多,制造出的影分身越强。

针对不同的作战情况,鸣人可以选择制造出各种强度的影分身,有的用来佯攻,有的用来发起致命一击。

那么问题来了,假设鸣人的查克拉能量为M,他影分身的个数为N,那么制造影分身时有多少种(用K表示)不同的分配方法?(影分身可以被分配到0点查克拉能量)

输入
第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。
输出
对输入的每组数据M和N,用一行输出相应的K。
样例输入
1
7 3
样例输出
8
#include <iostream>

using namespace std;

int apple(int m, int n)
{
if(n==1||m==0)
return 1;
if(n>m)
return apple(m, m);
if(n<=m)
return apple(m, n-1) + apple(m-n, n);
}

int main()
{
int t;
cin>>t;
while(t--)
{
int M, N;
cin>>M>>N;
cout<<apple(M, N)<<endl;
}
return 0;
}

分析:把分身看做盘子,查克拉看做苹果。本题是放苹果问题的变式

dp方法

#include<bits/stdc++.h>
using namespace std;

#define maxn 10

int n,m;
int f[maxn+5][maxn+5]={0};

int main(){
for(int i=0;i<=maxn;i++) f[0][i]=1;
for(int i=1;i<=maxn;i++){
for(int j=1;j<=maxn;j++){
if(j<=i) f[i][j]=f[i][j-1]+f[i-j][j];
else f[i][j]=f[i][i];
}
}

int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&m,&n);
printf("%d\n",f[m][n]);
}
return 0;
}

8471:切割回文
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
阿福最近对回文串产生了非常浓厚的兴趣。

如果一个字符串从左往右看和从右往左看完全相同的话,那么就认为这个串是一个回文串。例如,“abcaacba”是一个回文串,“abcaaba”则不是一个回文串。

阿福现在强迫症发作,看到什么字符串都想要把它变成回文的。阿福可以通过切割字符串,使得切割完之后得到的子串都是回文的。

现在阿福想知道他最少切割多少次就可以达到目的。例如,对于字符串“abaacca”,最少切割一次,就可以得到“aba”和“acca”这两个回文子串。

输入
输入的第一行是一个整数 T (T <= 20) ,表示一共有 T 组数据。
接下来的 T 行,每一行都包含了一个长度不超过的 1000 的字符串,且字符串只包含了小写字母。
输出
对于每组数据,输出一行。该行包含一个整数,表示阿福最少切割的次数,使得切割完得到的子串都是回文的。
样例输入
3
abaacca
abcd
abcba
样例输出
1
3
0
提示
对于第一组样例,阿福最少切割 1 次,将原串切割为“aba”和“acca”两个回文子串。
对于第二组样例,阿福最少切割 3 次,将原串切割为“a”、“b”、“c”、“d”这四个回文子串。
对于第三组样例,阿福不需要切割,原串本身就是一个回文串。

思路: dp[i]表示把前i个都变成回文串最少需要切割的次数。 每次枚举在j后面切一刀,暴力判断(j+1,i)是否是回文,如果是,那就是要切割dp[j]+1次。取最小即可。

#include <iostream>

using namespace std;

string str;
int dp[1005];

bool isHui(int st, int en)
{
while(st<en)
{
if(str[st]!=str[en])
return false;
st++;
en--;
}
return true;
}

int main()
{
int T;
cin>>T;
while(T--)
{
cin>>str;
for(int i=0;i<str.size();i++)
{
dp[i]=(isHui(0,i))?0:i;//dp[i]初始化
for(int j=0;j<i;j++)
{
if(isHui(j+1, i))
dp[i]=min(dp[i], dp[j]+1);
}
}
cout<<dp[str.size()-1]<<endl;
}

return 0;
}

8780:拦截导弹
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹。

输入
第一行是一个整数N(不超过15),表示导弹数。
第二行包含N个整数,为导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数)。
输出
一个整数,表示最多能拦截的导弹数。
样例输入
8
389 207 155 300 299 170 158 65
样例输出
6
#include <iostream>

using namespace std;

int dp[18], A[18];
int main()
{
int N, Max=0;
cin>>N;
for(int i=1;i<=N;i++)
cin>>A[i];
for(int i=1;i<=N;i++)
{
dp[i]=1;
for(int j=1;j<i;j++)
{
if(A[i]<=A[j]&&dp[j]+1>dp[i])
dp[i]=dp[j]+1;
}
Max=max(Max, dp[i]);
}
cout<<Max;
return 0;
}

8782:乘积最大
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友XZ也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目:

设有一个长度为N的数字串,要求选手使用K个乘号将它分成K+1个部分,找出一种分法,使得这K+1个部分的乘积能够为最大。

同时,为了帮助选手能够正确理解题意,主持人还举了如下的一个例子:

有一个数字串:312,当N=3,K=1时会有以下两种分法:

1) 3*12=36

2) 31*2=62

这时,符合题目要求的结果是:31*2=62

现在,请你帮助你的好朋友XZ设计一个程序,求得正确的答案。

输入
程序的输入共有两行:
第一行共有2个自然数N,K(6≤N≤40,1≤K≤6)
第二行是一个长度为N的数字串。
输出
输出所求得的最大乘积(一个自然数)。(保证最终答案不超过int范围)
样例输入
4 2
1231
样例输出
62
#include <iostream>

using namespace std;

const int maxn=50;
int a[maxn][maxn];
int dp[maxn][maxn];

int main()
{
int N, K;
cin>>N>>K;
char ch;
for(int i=1;i<=N;i++)
{
cin>>ch;
a[i][i]=ch-'0';
}
for(int i=1;i<=N;i++)
{
for(int j=i+1;j<=N;j++)
{
a[i][j]=a[i][j-1]*10+a[j][j];
}
}
for(int i=1;i<=N;i++)
dp[i][0]=a[1][i];
for(int i=1;i<=N;i++)
{
for(int j=1;j<=K;j++)
{
for(int p=1;p<i;p++)
dp[i][j]=max(dp[i][j], dp[p][j-1]*a[p+1][i]);
}
}
cout<<dp[N][K];

return 0;
}

可以看出本题就是一个划分问题,要求一个最优划分。

d[i][j]表示到i为止划分成j个数的最大乘积,则有转移方程:

d[i][j]=max{d[k][j-1]*num[k+1][i]}

num[s][t]是区间st所代表的数,可以离线求出以加快速度。


8785:装箱问题
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
有一个箱子容量为V(正整数,0<=v<=20000),同时有n个物品(0< n<=30),每个物品有一个体积(正整数)。

要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

输入
第一行是一个整数V,表示箱子容量。
第二行是一个整数n,表示物品数。
接下来n行,每行一个正整数(不超过10000),分别表示这n个物品的各自体积。
输出
一个整数,表示箱子剩余空间。
样例输入
24
6
8
3
12
7
9
7
样例输出
0

标准的01背包

#include <iostream>

using namespace std;

const int maxn=20005;
int a[maxn], dp[maxn];

int main()
{
int V, n, Max=0;
cin>>V>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
for(int v=V;v>=a[i];v--)
{
dp[v]=max(dp[v], dp[v-a[i]]+a[i]);
Max=max(Max, dp[v]);
}
}
cout<<V-Max;
return 0;
}

8786:方格取数
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
设有N*N的方格图(N<=10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示(见样例):< p="">



某人从图的左上角的A 点出发,可以向下行走,也可以向右走,直到到达右下角的B点。在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。 此人从A点到B 点共走两次,试找出2条这样的路径,使得取得的数之和为最大。

输入
输入的第一行为一个整数N(表示N*N的方格图),接下来的每行有三个整数,前两个表示位置,第三个数为该位置上所放的数。一行单独的0表示输入结束。
输出
只需输出一个整数,表示2条路径上取得的最大的和。
样例输入
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
样例输出
67
来源
NOIP2000复赛 提高组 第四题

8786:方格取数

思路:

多线程DP ,同时模拟两个人走。

O(n^4)
f[i][j][k][l]表示分别走到(i,j)和(k,l)的最大和。
每次从上一步分别走(下,下),(右,右),(右,下),(下,右)的状态推导就好了。
f[i][j][k][l]=max(f[i-1][j][k-1][l],f[i][j-1][k][l-1],f[i][j-1][k-1][l],f[i-1][j][k][l-1])+a[i][j]+a[k][l]-((i==j&&k==l)?a[k][l]:0);
#include <iostream>

using namespace std;

const int maxn=15;
int a[maxn][maxn];
int dp[maxn][maxn][maxn][maxn];

int main()
{
int N;
cin>>N;
int tmp;
int x,y,val;
while(true)
{
cin>>x>>y>>val;
if(x==0&&y==0&&val==0)
break;
a[x][y]=val;
}

for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
for(int k=1;k<=N;k++)
{
for(int r=1;r<=N;r++)
{
if(i==k&&j==r)
tmp=a[i][j];
else
tmp=0;
dp[i][j][k][r]=max( max(dp[i-1][j][k-1][r], dp[i][j-1][k][r-1]) ,max(dp[i-1][j][k][r-1], dp[i][j-1][k-1][r])) + a[i][j]+a[k][r] -tmp;
}
}
}
}
cout<<dp[N][N][N][N];

return 0;
}

8787:数的划分
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。

例如:n=7,k=3,下面三种分法被认为是相同的。

1,1,5; 1,5,1; 5,1,1;

问有多少种不同的分法。 输出:一个整数,即不同的分法。

输入
两个整数n,k (6 < n <= 200,2 <= k <= 6),中间用单个空格隔开。
输出
一个整数,即不同的分法。
样例输入
7 3
样例输出
4
提示
四种分法为:1,1,5;1,2,4;1,3,3;2,2,3。
来源
NOIP2001复赛 提高组 第二题

类似:放苹果问题,只不过要求不空,那就每一个盘子先放一个

#include <iostream>

using namespace std;

int apple(int m, int n)
{
if(n==1||m==0)
return 1;
if(n>m)
return apple(m, m);
if(n<=m)
return apple(m, n-1) + apple(m-n, n);
}

int main()
{
int n, k;
cin>>n>>k;
cout<<apple(n-k,k);
return 0;
}

90:滑雪
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
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

参考1

参考2


9265:取数游戏
查看 提交 统计 提问
总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 131072kB
描述
我们来玩一个游戏:自然数1到N,按顺序列成一排,你可以从中取走任意个数,但是相邻的两个不可以同时被取走。如果你能算出一共有多少种取法,那么你会被天神Lijiganjun奖励。

输入
仅包含一个数n(1< n < 50)。

输出
仅包含一个数———你的答案。

样例输入
5
样例输出
13
来源
递推五十题
可能很多人都知道是一个类似于斐波那契数列的东西,然后递推求解。但是估计很少人知道为什么,我钻研了一下,说说自己的见解。

有一排数 1,2,..n-1,n

f[i]表示(前)i个数取的方式数,现在已知f[n-1] f[n-2],求f[n]

第n个数有两种状态,取或不取,如果取,那么n-1就不能取(题目条件),所以方案数就是f[n-2](在此中每种方案里加一个4即可),另一种是不取,那么就是f[n-1](3不一定取),所以总的就是f[n]:=f[n-1]+f[n-2],证明完毕!
#include <iostream>

using namespace std;

long long p[55];

int main()
{
int n;
cin>>n;
p[1]=2;
p[2]=3;
for(int i=3;i<=n;i++)
p[i]=p[i-1]+p[i-2];
cout<<p[n];

return 0;
}

9267:核电站
查看 提交 统计 提问
总时间限制: 5000ms 单个测试点时间限制: 1000ms 内存限制: 131072kB
描述
一个核电站有N个放核物质的坑,坑排列在一条直线上。如果连续M个坑中放入核物质,则会发生爆炸,于是,在某些坑中可能不放核物质。

任务:对于给定的N和M,求不发生爆炸的放置核物质的方案总数

输入
只一行,两个正整数N,M( 1 < N < 50,2 ≤ M ≤ 5 )

输出
一个正整数S,表示方案总数。

样例输入
4 3
样例输出
13

参考

dp[n]表示在n个坑中,每个坑都有两种可能,放或者不放,但不能有连续m个坑里都有物质

从头开始向后放,每个坑都有两种可能,放或者不放

开头前i个连续的坑中都有核物质(0<=i<=m-1),则第i+1个坑必空。 i+1后面的坑再放和前面的就又没关系了

i=0时的放法为dp[n-1]; 在后n-1个坑中,每个坑都有两种可能,放或者不放,但不能有连续m个坑里都有物质
i=1时的放法为dp[n-2]; 在后n-2个坑中…………
……………………;
i=m-1时的放法为dp[n-m]。 在后n-m个坑中…………

得dp[n]=dp[n-1]+dp[n-2]+……+dp[n-m] 。

当n<=m-1时: dp[n]=2*dp[n-1] (无论放还是不放,都不会有连续m个坑里都有)

当n==m时: dp[n]=2*dp[n-1] -1(减去每个坑里都有核物质这种情况)

当n>m时:
dp[n]=dp[n-1]+dp[n-2]+……+dp[n-m]
dp[n-1]=dp[n-2]+……+dp[n-m]
两式相减得:
dp[n]=dp[n-1]*2-dp[n-m-1]
#include <iostream>

using namespace std;

long long dp[55];

int main()
{
int N, m;
cin>>N>>m;
dp[0]=1;
for(int i=1;i<=N;i++)
{
if(i<m)
dp[i]=dp[i-1]*2;
else if(i==m)
dp[i]=dp[i-1]*2-1;
else
dp[i]=dp[i-1]*2-dp[i-m-1];
}
cout<<dp[N];

return 0;
}

9268:酒鬼
查看 提交 统计 提问
总时间限制: 2000ms 单个测试点时间限制: 1000ms 内存限制: 131072kB
描述
Santo刚刚与房东打赌赢得了一间在New Clondike 的大客厅。今天,他来到这个大客厅欣赏他的奖品。房东摆出了一行瓶子在酒吧上。瓶子里都装有不同体积的酒。令Santo高兴的是,瓶子中的酒都有不同的味道。房东说道:“你可以喝尽可能多的酒,但是一旦打开酒盖你就必须把它喝完,喝完一瓶后把它放回原处。还有一件最重要的事,你必须从左至右依次喝,并且不能连续超过三瓶,不然会给你带来坏运气。”现在可怜的Santo站在酒吧前努力的想着,他到底应该喝哪几瓶才能使喝的酒最多呢?请帮助他找出他应该喝的酒瓶号,因为思考让他感到不安。

输入
第一行一个整数N,有N个酒瓶。N<=700接下有N行,第I+1行的数字代表酒瓶I中酒的体积。

输出
一个数字,喝的酒的最大总体积。遵守以上规则,使得三个连续瓶子中至少一个瓶子是满的。

样例输入
6
6
10
13
9
8
1
样例输出
33
#include <iostream>

using namespace std;

int a[705], dp[705];

int main()
{
int N;
cin>>N;
for(int i=1;i<=N;i++)
cin>>a[i];
dp[1]=a[1];
dp[2]=dp[1]+a[2];
for(int i=3;i<=N;i++)
{
dp[i]=max(dp[i-1], max(dp[i-2]+a[i], dp[i-3]+a[i]+a[i-1]));
}
cout<<dp[N];
return 0;
}
思路:

d[i]的意思是分析到第i个酒瓶时所能喝的最多酒。

状态转移方程为:

d[i] = max(d[i - 1], max(d[i - 2] + a[i], d[i - 3] + a[i] + a[i - 1]));

9271:奶牛散步
查看 提交 统计 提问
总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 131072kB
描述
从一个无限大的矩阵的中心点出发,一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点
共有多少种走法?

输入
一个数字,代表N,N<=1000

输出
输出有多少方案, 模12345

样例输入
2
样例输出
7
#include <iostream>

using namespace std;

int dp[1005];

int main()
{
int N;
cin>>N;
dp[1]=3;
dp[2]=7;
for(int i=3;i<=N;i++)
dp[i]=(dp[i-1]*2 + dp[i-2])%12345;
cout<<dp[N];
return 0;
}



f[i][j]表示i位数中含数字3的个数模2为j的个数。于是分第i位填3还是不填3讨论。

dp[i][1]表示i位数有奇数个三的数量,
dp[i][0]表示有偶数个三的数量。
dp[i][1]可以从dp[i-1][1]首位添加0 1 2 4 5 6 7 8 9和dp[i-1][0]首位添加3转移,dp[i][0]同理。
注意当i==N时首位不能添加0
#include <cstdio>
int N;
int dp[1010][2];

/*
用dp[i][1]表示i位数有奇数个三的数量,
dp[i][0]表示有偶数个三的数量。
dp[i][1]可以从dp[i-1][1]首位添加0 1 2 4 5 6 7 8 9和dp[i-1][0]首位添加3转移,
dp[i][0]同理。注意当i==N时首位不能添加0。
*/

int main(){
scanf("%d",&N);
dp[1][1]=1;
dp[1][0]=9;
for(int i=2;i<=N;++i){
int k = i==N?8:9;
dp[i][0]=(dp[i-1][0]*k+dp[i-1][1])%12345;
dp[i][1]=(dp[i-1][1]*k+dp[i-1][0])%12345;
}
printf("%d",dp[N][0]);
return 0;
}

9277:Logs Stacking堆木头
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 131072kB
描述
Daxinganling produces a lot of timber. Before loading onto trains, the timberjacks will place the logs to some place in the open air first. Looking from the sideway, the figure of a logs stack is as follows:
We have known that the number of logs in each layer is fewer than the lower layer for at least one log, and that in each layer the logs are connected in a line. In the figure above, there are 12 logs in the bottom layer of the stack. Now, given the number of logs in the bottom layer, the timberjacks want to know how many possible figures there may be.
给出在最底层的木头的个数,问有多少种堆放木头的方式,当然你的堆放方式不能让木头掉下来.
在堆放的时候木头必须互相挨着在一起.

输入
The first line of input contains the number of test cases T (1 <= T <= 1000000). Then T lines follow. Every line only contains a number n (1 <= n <= 200000) representing the number of logs in the bottom layer.

输出
For each test case in the input, you should output the corresponding number of possible figures. Because the number may be very large, just output the number mod 10^5.

样例输入
4
1
2
3
5
样例输出
1
2
5
34
提示
当输入3时,有5种方式

第一种:上面一个也不放

第二种:上面放一根,放在最左边

第三种:上面放一根,放在最右边

第四种:上面放二根

第五种:上面先放二根,然后在二根的上面放一根

参考

Contents