動態規劃題。開始的時候用狀態dp[i][j]表示最多i張郵票，能否組成j元。這樣時間復雜度為O(n*n*k*10000)結果TLE了。
先貼個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;
}
后來實在想不出來如何優化了。。?？戳讼氯ツ曜约簩懙拇a...Orz..
用dp[i]表示組成i所需要的最少的郵票數。這樣當dp[i]>k時，說明不能用k張郵票組成i了。時間復雜度為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足夠了，因為k<=200.用INT_MAX表示無窮大，加一個數的時候會溢出
????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;
}