動(dòng)態(tài)規(guī)劃題。開始的時(shí)候用狀態(tài)dp[i][j]表示最多i張郵票，能否組成j元。這樣時(shí)間復(fù)雜度為O(n*n*k*10000)結(jié)果TLE了。
先貼個(gè)TLE的代碼：
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?fin("stamps.in");
ofstream?fout("stamps.out");
#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif
int?k,n;
bool?dp[200*10000+1];
int?stamps[50];
void?solve()
{
????in>>k>>n;
????for(int?i=0;i<n;++i)
????????in>>stamps[i];
????sort(&stamps[0],&stamps[n]);
????int?maximum?=?stamps[n-1]*k;
????dp[0]?=?true;
????for(int?i=0;i<k;++i){
????????for(int?j=maximum;j>=0;j--){
????????????if(!dp[j])
????????????for(int?x=0;x<n;++x){
????????????????if(j>=stamps[x]&&dp[j-stamps[x]]){
????????????????????dp[j]=true;
????????????????????break;
????????????????}
????????????}
????????}
????}
????int?res;
????for(res=1;res<=maximum&&dp[res];++res);
????out<<res-1<<endl;
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}
后來實(shí)在想不出來如何優(yōu)化了。。。看了下去年自己寫的代碼...Orz..
用dp[i]表示組成i所需要的最少的郵票數(shù)。這樣當(dāng)dp[i]>k時(shí)，說明不能用k張郵票組成i了。時(shí)間復(fù)雜度為O(10000*k*n)。
代碼如下：
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?fin("stamps.in");
ofstream?fout("stamps.out");
#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif
int?k,n;
int?dp[200*10000+2];
int?stamps[50];
void?solve()
{
????in>>k>>n;
????for(int?i=0;i<sizeof(dp)/sizeof(int);++i)
????????dp[i]?=1000; //1000用作表示infinite足夠了，因?yàn)閗<=200.用INT_MAX表示無窮大，加一個(gè)數(shù)的時(shí)候會(huì)溢出
????for(int?i=0;i<n;++i){
????????in>>stamps[i];
????}
????sort(&stamps[0],&stamps[n]);
????int?maximum?=?stamps[n-1]*k;
????dp[0]=0;
????for(int?i=0;i<n;++i)
????????for(int?j=stamps[i];j<=maximum;++j){??????
???????????????dp[j]?=min(dp[j],dp[j-stamps[i]]+1);
????????}
????for(int?i=1;i<=maximum;++i){
????????if(dp[i]>k){
????????????out<<i-1<<endl;
????????????return;
????????}
????}
????out<<maximum<<endl;
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}