hdu 1963 Investment(完全背包)

点击打开链接hdu 1963

思路: 完全背包
分析:
1 根据题目很容易分析出题目是裸的完全背包，但是经过题目的条件我们发现dp数组开不下（怒RE不解释）
2 然后发现题目说了所有的bonds的value都是1000的整数倍，因此这边我们把sum和所有value都除以1000这样就降低了空间，那么dp数组就可以开的下了

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 11;
const int MAXN = 1000010;

int sum , year , n , v[N] , w[N];
long long ans , dp[MAXN];

void solve(){
    ans = sum;
    sum /= 1000;
    memset(dp , 0 , sizeof(dp));
    for(int i = 1 ; i <= n ; i++)
        for(int j = v[i] ; j < MAXN ; j++) 
            dp[j] = max(dp[j] , dp[j-v[i]]+w[i]);
    while(year--)
        ans += dp[ans/1000]; 
    printf("%lld\n" , ans);
}

int main(){
    int Case;
    scanf("%d" , &Case);
    while(Case--){
        scanf("%d%d" , &sum , &year); 
        scanf("%d" , &n);
        for(int i = 1 ; i <= n ; i++){
            scanf("%d%d" , &v[i] , &w[i]); 
            v[i] /= 1000;
        }
        solve();
    }
    return 0;
}