P1616 疯狂的采药 （完全背包优化）

（点击此处查看原题）

题意

简单来说，就是一个完全背包，不过这里卡住了常规的完全背包写法，时间复杂度为O（ V*∑( V/c[i] )）如下所示：

for(int i = ;i <= n ;i ++)

    {

        scanf("%d%d",cost+i,val+i);

        for(int j = t; j >= cost[i] ; j --)

        {

            for(int k = ; k * cost[i] <= j ;k ++)

            {

                dp[j] = max(dp[j],dp[j-k*cost[i]] + k * val[i]);

            }

        }

    }

解题思路

既然普通的写法无法解决，那就采用如下的优化即可,时间复杂度为O(NV),题目满足N*T <= 1e7，因此可以跑过去：

for(int i = ;i <= n ;i ++)

    {

        scanf("%d%d",cost+i,val+i);

        for(int j = cost[i]; j <= t; j ++)

        {

            dp[j] = max(dp[j],dp[j-cost[i]] + val[i]);

        }

    }

代码区

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<string>

#include<fstream>

#include<vector>

#include<stack>

#include <map>

#include <iomanip>

#define bug cout << "**********" << endl

#define show(x, y) cout<<"["<<x<<","<<y<<"] "

#define LOCAL = 1;

using namespace std;

typedef long long ll;

const int inf = 1e9 + ;

const ll mod = 1e9 + ;

const int Max = 1e5 + ;

int t, n;

int cost[Max],val[Max];

int dp[Max];            //记录价格为i的时候的最大价值

int main()

{

#ifdef LOCAL

    //    freopen("input.txt", "r", stdin);

    //    freopen("output.txt", "w", stdout);

#endif

    scanf("%d%d",&t,&n);

    memset(dp,,sizeof(dp));

    for(int i = ;i <= n ;i ++)

    {

        scanf("%d%d",cost+i,val+i);

        for(int j = cost[i]; j <= t; j ++)

        {

            dp[j] = max(dp[j],dp[j-cost[i]] + val[i]);

        }

    }

    printf("%d\n",dp[t]);

    return ;

}