1475.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<vector>
#include<iostream>
using namespace std;
void add(vector<int> & d,vector<int> & s){
    int i;
	for(i=499;i>=0;i--){
        d[i]+=s[i];
		if(d[i]>9) {d[i-1]+=d[i]/10;d[i]%=10;}
	}
}
void mul(vector<int> & d,int k){
    int i;
	for(i=0;i<499;i++) d[i]*=k;
	for(i=499;i>=0;i--){
		if(d[i]>9) {d[i-1]+=d[i]/10;d[i]%=10;}
	}
}
int main(){
    int i,j;
    vector<int> atemp(500,0);
	vector<vector<int> > aaa(201,atemp);
	vector<vector<vector<int> > > num(201,aaa);
	for(i=1;i<=200;i++) num[i][1][499]=1;
    for(i=2;i<=200;i++){
		cout<<i<<endl;
		for(j=2;j<=i;j++){
			if(i-1>=1&&i-1>=j)
            add(num[i][j],num[i-1][j]);
			if(i-1>=1&&j-1>=1)
			add(num[i][j],num[i-1][j-1]);
			mul(num[i][j],j);
		}
	}
}