DP递归打表

2017-01-02 08:24:46来源:CSDN作者:qq_33785671人点击

第七城市
//PKU2506Tiling  DP递归+高精度+打表//DP递推 C[i]=C[i-1]+C[i-2]*2//高精度 //打表 #include<iostream>#include<cstdio>#include<cmath>#include<cstring>using namespace std;int shz[255][500];int main(){ memset(shz,0,sizeof(shz)); shz[1][0]=1;//大整数位数  shz[1][1]=1;//大整数各位 shz[2][0]=1; shz[2][1]=3; for(int i=3;i<255;i++){  int dc=max(shz[i-1][0],shz[i-2][0]);  shz[i][0]=dc;  for(int j=1;j<=dc;j++)   shz[i][j]+=shz[i-1][j]+shz[i-2][j]*2;  for(int j=1;j<=dc;j++){   shz[i][j+1]+=shz[i][j]/10;   shz[i][j]%=10;  }  while(shz[i][shz[i][0]+1]){   shz[i][shz[i][0]+2]=shz[i][shz[i][0]+1]/10;   shz[i][shz[i][0]+1]%=10;   shz[i][0]++;  } } int a; while(cin>>a){  if(a==0)cout<<"1"<<endl;  else{   for(int i=shz[a][0];i>=1;i--)    cout<<shz[a][i];   cout<<endl;  } }  return 0;}//poj 放苹果//DP递推打表 //如果苹果个数小于盘子个数,则有盘子空着 C[i,j]=C[i,i]//如果苹果个数大于等于盘子个数分两种情况//一是所有盘子都有苹果,则每个盘子抽掉一个的分法个数等于i-j的,二是有盘子空着,则增加盘子没有增加分法个数,等效于将新增加的盘子空着就可以可//所以C[i][j]=C[i][j-1]+C[i-j][j]//C[1][1]=1#include<iostream>#include<cstdio>using namespace std;int shz[15][15];int main(){ for(int i=0;i<=10;i++){  for(int j=1;j<=10;j++){   if(i==0)shz[i][j]=1;   else if(j==1)shz[i][j]=1;   else{    if(i<j)shz[i][j]=shz[i][i];    else     shz[i][j]=shz[i][j-1]+shz[i-j][j];   }  } } int a; cin>>a; for(int i=0;i<a;i++){  int b,c;  cin>>b>>c;  cout<<shz[b][c]<<endl; } return 0;}//poj 3525:上台阶//DP递推打表//反过来想,从第n阶到第一阶与从第一阶到第n介效果相同//那么从第n阶有三种走法,一步或者两步或者三步//则 C[n]=C[n-1]+C[n-2]+C[n-3]#include<iostream>#include<cstdio>using namespace std;int shz[100+5];int main(){    shz[1]=1;    shz[2]=2;    shz[3]=4;    for(int i=4;i<=100;i++)        shz[i]=shz[i-1]+shz[i-2]+shz[i-3];    int a;    while(cin>>a&&a)        cout<<shz[a]<<endl;    return 0; } 
第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台