PKU 1032-Parliament

1032 Parliament - PKU Wiki*

解法

動的計画法．
答えが大きすぎる値になるのでlogを取る．
1001x1001x1001だと間に合わないが，答えが取る最大の値は45なので1001x45x1001ぐらいに直すことが出来るので間に合う．

実装(C++)

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
short next[1001][100];
double dp[1001][100];
double log_d[1001];
double solve(int x,int m){
	if(m>=60)return -9999999;
	if(x==0)return 0.0;
	if(x<m)return -9999999;
	if(dp[x][m]!=-1)return dp[x][m];
	double res=-999999;
	for(int s=m;s<=x;s++){
		if(solve(x-s,s+1)+log_d[s]>res){
			res=solve(x-s,s+1)+log_d[s];
			next[x][m]=s;
		}
	}
	return dp[x][m]=res;
}
int main() {
	int n;
	for(int i=0;i<1001;i++){
		for(int j=0;j<100;j++){
			dp[i][j]=-1;
		}
		log_d[i]=log(i);
	}
	cin>>n;
	solve(n,1);
	vector<int> res;
	int x=n,s=1;
	while(x){
		int nex=next[x][s];
		res.push_back(nex);
		x=x-nex;
		s=nex+1;
	}
	for(int i=0;i<res.size();i++){
		if(i)cout<<" ";cout<<res[i];
	}
	cout<<endl;
	return 0;
}