ZOJ 2224 Investment （完全背包）

水深无声 2024-02-17 21:26 7阅读 0赞

Investment

--------------------

Time Limit: 10 Seconds  Memory Limit: 32768 KB

--------------------

John never knew he had a grand-uncle, until he received the notary��s letter. He learned thathis late grand-uncle had gathered a lot of money, somewhere in South-America, and thatJohn was the only inheritor.

John did not need that much money for the moment. But he realized that it would be agood idea to store this capital in a safe place, and have it grow until he decided to retire. Thebank convinced him that a certain kind of bond was interesting for him.

This kind of bond has a fixed value, and gives a fixed amount of yearly interest, payedto the owner at the end of each year. The bond has no fixed term. Bonds are available indifferent sizes. The larger ones usually give a better interest. Soon John realized that theoptimal set of bonds to buy was not trivial to figure out. Moreover, after a few years hiscapital would have grown, and the schedule had to be re-evaluated.

Assume the following bonds are available:

<table> 
 <tbody> 
  <tr> 
   <td>Value</td> 
   <td>Annual interest</td> 
  </tr> 
  <tr> 
   <td>4000</td> 
   <td>400</td> 
  </tr> 
  <tr> 
   <td>3000</td> 
   <td>250</td> 
  </tr> 
 </tbody> 
</table>

With a capital of 10000 one could buy two bonds of 4000, giving a yearly interest of800. Buying two bonds of 3000, and one of 4000 is a better idea, as it gives a yearlyinterest of 900. After two years the capital has grown to 11800, and it makes sense to sella 3000 one and buy a 4000 one, so the annual interest grows to 1050. This is where thisstory grows unlikely: the bank does not charge for buying and selling bonds. Next year thetotal sum is 12850, which allows for three times 4000, giving a yearly interest of 1200.

Here is your problem: given an amount to begin with, a number of years, and a set ofbonds with their values and interests, find out how big the amount may grow in the givenperiod, using the best schedule for buying and selling bonds.

**Input**

The first line contains a single positive integer N which is the number of test cases. The testcases follow.

The first line of a test case contains two positive integers: the amount to start with (atmost 1000000), and the number of years the capital may grow (at most 40).

The following line contains a single number: the number d (1 <= d <= 10) of availablebonds.

The next d lines each contain the description of a bond. The description of a bond consistsof two positive integers: the value of the bond, and the yearly interest for that bond. Thevalue of a bond is always a multiple of 1000. The interest of a bond is never more than10% of its value.

**Output**

For each test case, output �C on a separate line �C the capital at the end of the period, after anoptimal schedule of buying and selling.

**Sample Input**

1  
10000 4  
2  
4000 400  
3000 250

**Sample Output**

14050

分析：完全背包问题，刚开始数组开为100w，结果seg了，然后开为1000w，结果ME了，然后看了讨论说，可以吧数组压缩，因为债券值是1000的整数倍，所以所拥有的本息和 的零头小于1000 不可能买到债券，所以，将本息和 与 债券值同时除以1000对正确结果没影响，这样就达到了优化数组。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define INF 10000000
    const int maxn=1e6+10;
    int dp[maxn];
    int bond[12],interes[12];
    int main() {
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		int start,year;
    		scanf("%d%d",&start,&year);
    		int d;
    		scanf("%d",&d);
    		for(int i=0;i<d;i++){
    			scanf("%d%d",&bond[i],&interes[i]);
    			bond[i]/=1000;
    		}
    		
    		int money=start;
    		while(year--){
    			int t=money/1000;
    			for(int i=1;i<=t;i++)
    			dp[i]=-INF;
    			dp[0]=0;
    			
    			for(int i=1;i<=t;i++){
    				for(int j=0;j<d;j++){
    				 if(i>=bond[j])
    				 dp[i]=max(dp[i],dp[i-bond[j]]+interes[j]);
    				}
    			}
    			
    			int cnt=0;
    			for(int i=t;i>=1;i--)
    			if(cnt<dp[i]){
    				cnt=dp[i];
    			}
    			money+=cnt;
    		}
    		
    		printf("%d\n",money);
    	}
    	return 0;
    }