1.codevs1742 爬楼梯
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
小明家外面有一个长长的楼梯，共N阶。小明的腿很长，一次能跨过一或两阶。有一天，他突发奇想，想求出从最低阶到最高阶共有几种爬楼梯的方案。你帮帮他吧！
输入描述 Input Description
一个整数N。
输出描述 Output Description
一个整数，为方案总数。
样例输入 Sample Input
5
样例输出 Sample Output
8
数据范围及提示 Data Size & Hint
0≤N≤40
#include<iostream> #include<cstdio> using namespace std; long long int a[41]; int n; int main() {scanf("%d",&n);if(n==0){cout<<0;return 0;}a[1]=1;a[2]=2;for(int i=3;i<=n;++i)a[i]=a[i-1]+a[i-2];cout<<a[n]<<endl;return 0; }
#include<iostream> int n; #include<cstring> using namespace std; #include<cstdio> const int INF=10001; int a[INF],b[INF],c[INF]; int lena=1,lenb=1,lenc=0; void count() {lenc=1;int x=0;while(lenc<=lenb||lenc<=lenb){c[lenc]=a[lenc]+b[lenc]+x;x=c[lenc]/10;c[lenc]%=10;lenc++;}c[lenc]+=x;if(c[lenc]==0)lenc--;return ; } void SWAP() {memset(a,0,sizeof(a));//strcpy(a,b);for(int i=1;i<=lenb;++i)a[i]=b[i];lena=lenb;memset(b,0,sizeof(b));for(int i=1;i<=lenc;++i)b[i]=c[i]; // strcpy(b,c);lenb=lenc;memset(c,0,sizeof(c));lenc=0; } int main() {scanf("%d",&n);a[1]=1;b[1]=2;for(int i=3;i<=n;++i){count();SWAP();}for(int i=lenb;i>=1;--i)printf("%d",b[i]);return 0; }
2.codevs1259 最大正方形子矩阵
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
在一个01矩阵中，包含有很多的正方形子矩阵，现在要求出这个01矩阵中，最大的正方形子矩阵，使得这个正方形子矩阵中的某一条对角线上的值全是1，其余的全是0。
输入描述 Input Description
第一行有两个整数n和m（1<=n,m<=1000）。接下来的n行，每行有m个0或1的数字。每两个数字之间用空格隔开。
输出描述 Output Description
只有一个整数，即这个满足条件的最大的正方形子矩阵的边长。
样例输入 Sample Input
4 6
0 1 0 1 0 0
0 0 1 0 1 0
1 1 0 0 0 1
0 1 1 0 1 0
样例输出 Sample Output
3
/*基本思路：统计每个点左上右各有多少个0（除自身以外），找最大正 方形子矩阵的时候，就以值为1的点，判断 他的左上（右上），上，左（右）各有多少个0，取一个小数后 加1，就是以当前这个点为左下角或者右下角的正方形的最大边长。 想法;因为题目中的1对角线是最难处理的，所以就把这个1作为突破口*/ #include<iostream> using namespace std; #include<cstdio> #define N 1001 int n,m; struct Poi{int l,r,num,ans,up; }; Poi poi[N][N]; int maxx=-N; void update() {for(int i=2;i<=n;++i)/*分别统计左上右各有多少个0*/for(int j=1;j<=m;++j){if(poi[i-1][j].num==0)poi[i][j].up=poi[i-1][j].up+1;}for(int j=2;j<=m;++j)for(int i=1;i<=n;++i){if(poi[i][j-1].num==0)poi[i][j].l=poi[i][j-1].l+1;}for(int j=m-1;j>=1;--j)for(int i=1;i<=n;++i)/*注意不同的寻找for循环的顺序是不同的*/{if(poi[i][j+1].num==0)poi[i][j].r=poi[i][j+1].r+1;} } void input() {scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){scanf("%d",&poi[i][j].num);}update(); } void countz()/*求左上方的正方形的最大边长*/ {for(int i=1;i<=m;++i)if(poi[1][i].num==1)poi[1][i].ans=1;for(int i=1;i<=n;++i)if(poi[i][1].num==1)poi[i][1].ans=1;for(int i=2;i<=n;++i)/*注意不同的寻找for循环的顺序是不同的*/for(int j=2;j<=m;++j){if(poi[i][j].num==1)poi[i][j].ans=min(min(poi[i][j].l,poi[i][j].up),poi[i-1][j-1].ans)+1;if(poi[i][j].ans>maxx)maxx=poi[i][j].ans;} } void county() {for(int i=1;i<=n;++i)poi[i][m].ans=1;for(int i=2;i<=n;++i)for(int j=m-1;j>=1;--j){if(poi[i][j].num==1)poi[i][j].ans=min(min(poi[i][j].r,poi[i][j].up),poi[i-1][j+1].ans)+1;if(poi[i][j].ans>maxx)maxx=poi[i][j].ans;} } int main() {input();countz();county();printf("%d\n",maxx);return 0; }
3. noi 1759:最长上升子序列（nlogn算法）
- 总时间限制:
- 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; #include<cstdio> const int INF=10001; #include<cstring> const int N=1001; long long a[N],c[N],f[N]; int search(int l,int r,int i)/*二分查找*/ {if(l==r) return l;int mid=(l+r+1)/2;if(c[mid]>=a[i]) return search(l,mid-1,i);/*等号加到上面是上升序列*/if(c[mid]<a[i]) return search(mid,r,i);/*等号加到下面是不下降*/ } int main() {int n;scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",&a[i]);memset(c,127,sizeof(c));long long int MAX=-INF;for(int i=1;i<=n;++i){f[i]=search(0,i,i)+1;c[f[i]]=min(c[f[i]],a[i]);MAX=max(f[i],MAX);}printf("%d\n",MAX);return 0; }
- 4.1166 矩阵取数游戏2007年NOIP全国联赛提高组时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
【问题描述】
帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m 的矩阵，矩阵中的每个元素aij均
为非负整数。游戏规则如下：
1. 每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；
2. 每次取走的各个元素只能是该元素所在行的行首或行尾；
3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分= 被取走的元素值*2i，
其中i 表示第i 次取数（从1 开始编号）；
4. 游戏结束总得分为m次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
输入描述 Input Description
第1行为两个用空格隔开的整数n和m。
第2~n+1 行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。
输出描述 Output Description
输出 仅包含1 行，为一个整数，即输入矩阵取数后的最大得分。
样例输入 Sample Input
2 3
1 2 3
3 4 2
样例输出 Sample Output
82
数据范围及提示 Data Size & Hint
样例解释
第 1 次：第1 行取行首元素，第2 行取行尾元素，本次得分为1*21+2*21=6
第2 次：两行均取行首元素，本次得分为2*22+3*22=20
第3 次：得分为3*23+4*23=56。总得分为6+20+56=82
【限制】
60%的数据满足：1<=n, m<=30, 答案不超过1016
100%的数据满足：1<=n, m<=80, 0<=aij<=1000
代码：
/*分析：对于区间型DP，f[i][j]，一般表示的不是i--j这个区间，而是从该开始延伸j位，这样在for循环中可以方便转移。 由题意，行与行之间没有关系，可以单独处理一行的问题。 考虑一行数据， 在区间[i..j]中取数可以转化为以下两种情况： 1.先取i，再在[i+1..j]中取； 2.先取j，再在[i..j-1]中取。 f(i,1)=2*a[i] f(i,j)=Max{2*f(i+1,j-1)+f(i,1),2*f[i,j-1]+f(i+j-1,1) 注意这里为什么没有题目中要求的2^x呢？因为当你把f[i+1][j-1]一层层推进去的时候，你会发现，其实在这个区间内部的数，会被乘了多次2，这就是题目中要求的后一个取的数比前一项多乘一个2. n<=80，须涉及到高精度运算。 位数估算：2^80*a[i]~2^90,十进制下大约27位。 注意数组f的清零初始化，否则会导致位数错误。 */ #include<iostream> using namespace std; #include<cstdio> #define N 1001 #define M 81 int a[M],n,m; int f[M][M][N],ans[N]; #include<cstring> void add(int *s,int *t)//s+=t {int len=max(s[0],t[0]);int i=1;while(i<=len){s[i]+=t[i];s[i+1]+=s[i]/10;s[i]%=10;i++;}if(s[len+1]) len++;s[0]=len; } int cmp(int *s,int *t)//t1>t2 fan hui zheng shu {if(s[0]>t[0]) return 1;if(t[0]>s[0]) return -1;for(int i=s[0];i>0;--i){if(s[i]>t[i]) return 1;if(t[i]>s[i]) return -1;}return 1; } void cpy(int *s,int* t )//ba t jia ren s {memset(s,0,sizeof(s));s[0]=t[0];for(int i=1;i<=t[0];++i)s[i]=t[i]; } int main() {scanf("%d%d",&n,&m);int t1[N],t2[N];for(int i=1;i<=n;++i)/*每输入一行就处理一行*/{memset(a,0,sizeof(a));memset(f,0,sizeof(f));for(int j=1;j<=m;++j){scanf("%d",&a[j]);//a[j]*=2;int len=1;for(len=1;a[j];++len){f[j][1][len]=a[j]%10;a[j]/=10;}/*注意点一：这里不能用add(f[j][1],f[j][1]),因为传入子函数中的是s，t虽然是相加，但是因为指针指的的是同一个地址，那么加的过程中，不仅s在变化，t也在变化，那就是不是我们想要的加法了;*/f[j][1][0]=len;cpy(t1,f[j][1]);add(f[j][1],t1);memset(t1,0,sizeof(t1));}for(int l=2;l<=m;++l){for(int j=1;j+l-1<=m;++j){memset(t1,0,sizeof(t1));memset(t2,0,sizeof(t2));add(t1,f[j+1][l-1]);add(t1,f[j+1][l-1]);add(t1,f[j][1]);/*动态规划方程不一定有相应的简短的形式*/add(t2,f[j][l-1]);add(t2,f[j][l-1]);add(t2,f[j+l-1][1]);if(cmp(t1,t2)>0)/*strcmp，和strcpy只适用于字符串，而不是用于int数组*/cpy(f[j][l],t1);else cpy(f[j][l],t2);}}add(ans,f[1][m]);}for(int i=ans[0];i>0;--i)printf("%d",ans[i]);printf("\n");return 0; }
