zoj 3211 dream city 贪心 dp和记忆化搜索

题目链接： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3374

题意：有n颗树，每棵树都有固定的初始值a[i],和有增长值b[i]，给出m天，每天只能砍一棵树，那么对与第j天，如果选择砍掉第i棵树，那么收获的硬币就是a[i]+b[i]*(j-1)，那么怎样

砍才能使收获的硬币最多

思路：此时，我们给出的贪心策略是：增长越快的树越晚砍，为什么？有人可能觉得如果一棵树的a[i]很大，尽管b[i]很小，放在后面也能得到较高的值，其实这样想是错的。

可以想下，要是我们已经得出了一种最优方案，砍掉了e颗树，那么我们所收获的硬币是不是就是 sum=a[1]+a[2]+b[2]+a[3]+(b[3]*2)+.......+a[e]+(b[e]*(e-10));进行下化简

sum=a[1]+a[2]+...+a[e]+b[2]+(b[3]*2)+....+(b[e]*(e-1))，可以看到，前面那一串a数组加起来的值是固定的，sum最后的值其实只和b什么时候砍有关，所以必须保证b越大越晚砍

每棵树可以选择砍与不砍，所以这是一个01背包问题，排完序后直接上01背包模板就行，下面给出记忆化搜搜和递推的写法

递推

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mp make_pair

using namespace std;

typedef pair<int,int> pii;

pii a[300];
int n,m,t,u,v;
int dp[300][300];

bool cmp(const pii a,const pii b)
{
    return a.second<b.second;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i].first);
        }
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i].second);
        }
        sort(a+1,a+n+1,cmp);//a是从1开始
        memset(dp,0,sizeof(dp));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                int res=(j-1)*a[i].second+a[i].first;
                dp[i][j]=dp[i-1][j];
                if(dp[i][j]<dp[i-1][j-1]+res)
                {
                    dp[i][j]=dp[i-1][j-1]+res;
                }
            }
        }
        printf("%d\n",dp[n][m]);
    }
}

记忆化搜索

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int,int> pii;

pii a[300];
int dp[300][300];
int n,m;


bool cmp(const pii a,const pii b)
{
    return a.second<b.second;
}

int dfs(int cur,int day)
{
    if(day>m||cur>n) return 0;
    if(dp[cur][day]!=-1) return dp[cur][day];
    int &res=dp[cur][day];
    res=max(dfs(cur+1,day),dfs(cur+1,day+1)+a[cur].first+a[cur].second*(day-1));
    return res;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i].first);
        }
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i].second);
        }
        sort(a+1,a+n+1,cmp);
        memset(dp,-1,sizeof(dp));
        int ans=dfs(1,1);
        printf("%d\n",ans);
    }
    return 0;
}