题目：

 

完全背包，参考背包九讲第二讲：

 

bond看成重量，interest看成价值，本金看成背包容量。

 

注意三点：

（1）本金每年不一样，更新；

（2）本金，债券都是1000的倍数，除以1000减少循环次数，是大大减少；

（3）本金的循环是从某债券到本金递增，不能搞反了。

 

代码：

#include 
     
      #include 
      
       #include 
       
        int f[50000];int bond[11],interest[11]; int main(){  int T,i,j,n,ans,tmp,t,start,year;  scanf("%d",&T);       do     {         scanf("%d%d",&start,&year);               scanf("%d",&n);                 memset(f,0,sizeof(f));         for(i = 0 ; i < n ; ++i)         {           scanf("%d%d",bond+i,interest+i);           bond[i] /= 1000;         }                   while(year--)         {           tmp = start;           tmp /= 1000;                        for(i = 0 ; i < n ; ++i)           for(j = bond[i] ; j <= tmp ; ++j)          // for(j = tmp ; j >= bond[i] ; --j)           {              t = f[j-bond[i]] + interest[i];              if(t > f[j]) f[j] = t;             }                       start += f[tmp];          }                  printf("%d\n",start);                                        }while(--T);     //system("pause");  return 0;    }