http://acm.pku.edu.cn/JudgeOnline/problem?id=1276
ok，这道题，的意思是给你一堆钱，各种面值的都有，比如10块的5张，5块的3张，2块的1张，请找出利用这些钱可以凑成的最接近且小于给定的数字cash的数额，比如cash=33块。
我们可以取3张10块+2张1块=32，就是我们可以找到的那个最接近且小于33的数额。
面额保存在D[n]数组里，相应的张数保存在N[n]数组里，考虑这个题目，实际上可以正向dp，也就是我们在及时加上面额D[i]时组成的钱的可能数额，可以利用前面D[0] …..D[i-1]的结果，这样我们只要保存下这些前面的可能组成的数额，比如我们用一个100001的bool数组元素sign[1000001],sign[i]保存能否组成该数额i。
然后最简单的是利用一个3重循环，但这样会tle
void solve_1(int D[20],int N[20],int cash,int n){
bool sign[2][MAX_N];
memset(sign,false,sizeof(sign[0])*2);
sign[0][0] = true;
int i;
for(i = 0 ; i < n ; i++){
for(int j = 0 ; j <= N[i] ; j++){
int temp = D[i]*j;
for(int k = 0 ; k+ temp <= cash ; k++){
if(sign[i%2][k])
sign[(i+1)%2][k+temp] = true;
}
}
}
int j;
for(j = cash ; j >= 0 ; j–){
if(sign[i%2][j]) break;
}
printf("%d\n",j);
}
实际上直接从0…..i得到0……i+1，i就代表了第i种面额，
比如可以利用前i项组合出x元，这样我们再利用循环，x+D[i+1]*j也是可以组合出来的
所以只需要枚举x和j就可以了。总的复杂度是n*max{N[i]}*100000
需要继续优化，
我们修改内层循环的先后顺序，我们首先从高到低枚举现在已经可以得到的现金额，从这个额度开始，让它不断扩充当前的一个新的可用面值D[i+1]。
比如我们已经得到现在可以得到的金额有
1 3 8 10 15,第i+1个面值为2，该面值纸币数目为3
这样我们从15开始，则可以得到15 17 19 21
从10开始，则可以得到10 12 14 16
从8开始，则可以得到8 10 12 14
看到了吧，优化的空间在这里，我们从8又来到了10，实际上我们发现10已经形成了就不用再往下进行了，优化的空间就在这里了。为了优化我们还需要额外记住形成当前面值所需要的D[i+1]的数额，如果我们后来又到了一个已经形成的面值，比较当前用掉的D[i+1]的个数，和以前的那个个数，如果大于以前的个数，显然不用继续进行了。
Problem: 1276
User: phylips Memory: 804K
Time: 0MS Language: G++
Result: Accepted
- Source Code
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define MAX_N 100001
#define MAX_INT 1000000
#define debug
#undef debug
using namespace std;
void solve(int D[20],int N[20],int cash,int n){
bool sign[MAX_N];
int sign_num[MAX_N];
memset(sign,false,sizeof(sign));
sign[0] = true;
int i;
for(i = 0 ; i < n ; i++){
memset(sign_num,MAX_INT,sizeof(sign_num));
for(int k = cash ; k >= 0 ; k–){
if(sign[k])
for(int j = 0 ; k+ D[i]*j <= cash && j <= N[i]; j++){
if(sign[k+D[i]*j] && j >= sign_num[k+D[i]*j]){
#ifdef debug
//printf("test:%d j:%d %d\n",k+D[i]*j,j,sign_num[k+D[i]*j]);
#endif
break;
}
else{
sign[k+D[i]*j] = true;
sign_num[k+D[i]*j] = j;
}
}
}
#ifdef debug
for(int t = 0 ; t < cash ; t++){
if(sign[t])printf("%d ",t);
}
printf("\n");
#endif
}
int j;
for(j = cash ; j >= 0 ; j–){
if(sign[j]) break;
}
printf("%d\n",j);
}
int main()
{
int cash,n;
int D[20],N[20];
while(scanf("%d%d",&cash,&n) == 2 ){
if(n==0)
{
printf("0\n");
continue;
}
for(int i = 0 ; i < n ; i++){
scanf("%d%d",&N[i],&D[i]);
}
solve(D,N,cash,n);
}
return 0;
}