动态规划题。开始的时候用状态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;
}
后来实在想不出来如何优化了。。。看了下去年自己写的代码...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;
}