posted @
2010-12-23 16:02 小阮 阅读(310) |
评论 (0) |
编辑 收藏
模拟1到359步就可以了。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei
TASK: spin
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
typedef struct Gap
{
int start;
int span;
}Gap;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int gap_num[5];
int speed[5];
Gap gaps[5][5];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
ifstream fin;
ofstream fout;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void move()
{
int i,j;
for(i=0; i<5; ++i)
for(j=0; j<gap_num[i]; ++j)
gaps[i][j].start = (gaps[i][j].start+speed[i])%360;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int tmp[360];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool check()
{
int i,j,k;
for(i=0; i<360; ++i) tmp[i]=0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<5; ++i)
for(j=0; j<gap_num[i]; ++j)
for(k=0; k<=gaps[i][j].span; ++k)
tmp[(gaps[i][j].start+k)%360]++;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<360; ++i)
if(tmp[i]==5)
return true;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return false;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,j;
fin.open("spin.in");
fout.open("spin.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=0; i<5; ++i)
{
fin>>speed[i];
fin>>gap_num[i];
for(j=0; j<gap_num[i]; ++j)
fin>>gaps[i][j].start>>gaps[i][j].span;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(check())
{
fout<<0<<endl;
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=1; i<360; ++i)
{
move();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(check())
{
fout<<i<<endl;
return 0 ;
}
}
fout<<"none"<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
posted @
2010-12-23 14:46 小阮 阅读(196) |
评论 (0) |
编辑 收藏
设要付的钱是M,存在一个付钱的上限V,对于0到V是一个多重背包问题(每种货币有限制数量)
对于给多的部分, 即V-M,由于还钱时候,每种货币没有数量限制,是一个完全背包问题。
参考这篇文章,
http://www.cppblog.com/Davidlrzh/articles/135614.html证明了,V 最大为 M + v[i]*v[i] (v[i]是货币中最大价值的一个)
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAXN = 25000;
const int MAX = 105;
const int INF = 99999;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int v[MAX], n[MAX];
int f[MAXN], g[MAXN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int V,N;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void ZeroOnePack(int c, int w, int dp[])
{
for(int v=V; v>=c; --v)
if(dp[v-c]+w < dp[v])
dp[v] = dp[v-c]+w;
return;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void CompletePack(int c, int w, int dp[])
{
for(int v=c; v<=V; ++v)
if(dp[v-c]+w < dp[v])
dp[v] = dp[v-c]+w;
return;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void MultiplePack(int c, int w, int m, int dp[])
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(m*c>=V)
{
CompletePack(c, w, dp);
return;
}
int k=1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(k<m)
{
ZeroOnePack(k*c, k, dp);
m-=k;
k*=2;
}
ZeroOnePack(m*c, m, dp);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int M;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i, max=0;
cin>>N>>M;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=1; i<=N; ++i)
{
cin>>v[i];
if(v[i]>max)
max=v[i];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=N; ++i)
cin>>n[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
V = M + max*max;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<V; ++i)
f[i] = INF;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=N; ++i)
MultiplePack(v[i], 1, n[i], f);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
V = max*max;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<V; ++i)
g[i] = INF;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=N; ++i)
CompletePack(v[i], 1, g);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
V = M+max*max;
int min = INF;
for(i=M; i<V; ++i)
if(f[i]+g[i-M]<min)
min = f[i]+g[i-M];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(min!=INF)
cout<<min<<endl;
else
cout<<-1<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2010-12-23 13:10 小阮 阅读(298) |
评论 (0) |
编辑 收藏
多重背包问题, 参考<<背包问题9讲>>
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAXN = 120005;
const int MAX = 15;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int c[MAX] , n[MAX];
int f[MAXN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int N,V;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
inline int max(int a, int b)
{
return a>b? a: b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void ZeroOnePack(int c, int w)
{
for(int v=V; v>=c; v--)
f[v] = max(f[v], f[v-c]+w);
return;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void CompletePack(int c, int w)
{
for(int v=c; v<=V; ++v)
f[v] = max(f[v], f[v-c]+w);
return;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void MultiplePack(int c, int w, int m)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(m*c>=V)
{
CompletePack(c, w);
return ;
}
int k=1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(k<m)
{
ZeroOnePack(k*c, k*w);
m -= k;
k*=2;
}
ZeroOnePack(m*c, m*w);
return ;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(cin>>V&&cin>>N)
{
if(!V&&!N) continue;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<=V; ++i) f[i]=0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=N; ++i)
cin>>n[i]>>c[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=N; ++i)
MultiplePack(c[i], c[i], n[i]);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
cout<<f[V]<<endl;
}
return 0;
}
posted @
2010-12-23 11:05 小阮 阅读(148) |
评论 (0) |
编辑 收藏
DP
f[i][j] 表示长度为i 的01串,1的个数不多于j的个数。
则对于第i位是0还是1,可分为两个子状态 f[i][j] = f[i-1][[j] + f[i-1][j-1]
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: kimbits
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
long long N,L,I;
long long f[100][100];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i,j;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ifstream fin("kimbits.in");
ofstream fout("kimbits.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>N>>L>>I;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<=N; ++i)
f[0][i] = f[i][0] = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=N; ++i)
for(j=1; j<=N; ++j)
f[i][j] = f[i-1][j] + f[i-1][j-1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=N; i>=1; --i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(I>f[i-1][L])
{
fout<<"1";
I -= f[i-1][L];
--L;
}else
fout<<"0";
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fout<<endl;
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2010-12-22 13:03 小阮 阅读(337) |
评论 (0) |
编辑 收藏
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: zerosum
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
const int num[] =
{1, 2, 3, 4, 5, 6, 7, 8, 9};
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
const char op[3] =
{' ', '+' , '-'};
char ans[8];
int n,N;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
ifstream fin;
ofstream fout;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int solve()
{
int sum = 0, last=1, flag=1;
for(int i=0, j=1; i<n-1; ++i, ++j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(ans[i] == op[1])
{
sum += last;
flag = 1;
last = num[j];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else if(ans[i] == op[2])
{
sum += last;
flag = -1;
last = -num[j];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
}else if(ans[i] == op[0])
{
last *=10;
last += flag*num[j];
}
sum += last;
return sum;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void output()
{
fout<<1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=0; i<n-1; ++i)
{
fout<<ans[i]<<num[i+1];
}
fout<<endl;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void dfs(int k)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(k==n-1)
{
int sum = solve();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(sum==0)
{
// solve();
output();
}
}else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=0; i<3; ++i)
{
ans[k] = op[i];
dfs(k+1);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
fin.open("zerosum.in");
fout.open("zerosum.out");
fin>>n;
dfs(0);
return 0;
}
posted @
2010-12-21 10:18 小阮 阅读(383) |
评论 (0) |
编辑 收藏
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: nocows
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int K = 105;
const int N = 205;
const int MOD = 9901;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int dp[K][N];
int s[K][N];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int k,n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i,j,m,c;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ifstream in("nocows.in");
ofstream out("nocows.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
in>>n>>k;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
dp[1][1]=1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=2; i<=k; ++i)
{
for(j=1; j<=n; j+=2)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(m=1; m<=j-1-m; m+=2)
{
if(m==j-1-m) c=1;
else c=2;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
dp[i][j] += c* ( dp[i-1][m]*s[i-2][j-1-m] +
dp[i-1][j-1-m]*s[i-2][m] +
dp[i-1][m]*dp[i-1][j-1-m] );
dp[i][j] %= MOD;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j=0; j<=n; ++j)
{
s[i-1][j] += dp[i-1][j] + s[i-2][j];
s[i-1][j] %= MOD;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
out<<dp[k][n]<<endl;
return 0;
}
posted @
2010-12-21 10:17 小阮 阅读(188) |
评论 (0) |
编辑 收藏
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: prefix
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
#include <string>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAXL = 200;
const int MAXN = 100000;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
string prim[MAXL+1];
int d[MAXL+1];
int m;
int ans;
string s;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,j,k, length;
string t;
ifstream in("prefix.in");
ofstream out("prefix.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=0; ;i++)
{
in>>t;
if(t == ".") break;
prim[i]=t;
d[i]=t.length();
}
m = i;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while(in>>t)
s.append(t);
length = s.length();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=0; i<length; ++i)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j=0; j<m; ++j)
{
if(i+d[j]>length) continue;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
bool f = false;
for(k=0; k<d[j]; ++k)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(s[i+k] != prim[j][k])
{
f = true;
break;
}
if(!f) ans = ans>i+d[j] ? ans : i+d[j];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
}
if(i+1>ans) break;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
out<<ans<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2010-12-21 10:16 小阮 阅读(484) |
评论 (1) |
编辑 收藏
每次相乘的结果去掉尾部的0 之后, mod 10000, 仅保留五位.
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: fact4
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
unsigned long res = 1;
ifstream fin("fact4.in");
ofstream fout("fact4.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>n;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=2; i<=n; ++i)
{
res *= i;
while(res%10==0)
res /=10;
res %= 100000 ;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fout<< res%10 <<endl;
return 0;
}
posted @
2010-12-21 10:14 小阮 阅读(125) |
评论 (0) |
编辑 收藏
其实类似可重背包问题, f[i] = min {f[i-cost[j]] + 1}
i表示背包容量,
cost[j]表示 第j种物品的消耗.
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei
TASK: stamps
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAXF = 2000000;
const int MAXN = 55;
const int INF = 0x7FFFFFFF;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int f[MAXF], cost[MAXN];
int N, K;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,j;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ifstream fin("stamps.in");
ofstream fout("stamps.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>K>>N;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
f[0] = 0 ;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<MAXF; ++i)
f[i] = INF;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1; i<=N; ++i)
fin>>cost[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j=1; j<MAXF; ++j)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=1; i<=N; ++i)
{
if(cost[i]<=j && f[j-cost[i]]+1 < f[j])
f[j] = f[j-cost[i]]+1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(f[j]>K)
{
fout<<j-1<<endl;
break;
}
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2010-12-20 11:14 小阮 阅读(132) |
评论 (0) |
编辑 收藏