B-happy card-基础DP

题目链接：http://acm.csust.edu.cn/problem/3028

Description

给你n个人，每一个人最多可以选

每一个人拿到不同数量的happy card 可以获得不同数量的欢乐值。

假如一个人拿到了

如果没有拿到happy card，则获得的欢乐值为0。

现在你需要把着

Input

第一行三个数字

接下来

保证

Output

最大的快乐值和

Sample Input 1

5 3 2
2 2 2 2 2
2 6 7

Sample Output 1

Sample Input 2

4 3 9
9 9 9 9 
1 2 3

Sample Output 2

一个DP题，对于萌新来讲可以有的难度。

列出所有条件：人数n，总的快乐牌num，限制手牌m

我们可以DP的是：前i个人在总牌数为j的情况下，第i个人拿k张牌的最大幸福值。想想似乎和01背包有点儿类似，那么状态转移方程也就不难写出来了：

dp[i][j]=max(dp[i-1][j-k]+h[k],dp[i][j]);当然我们的第一维其实可以直接滚动掉的。。

其实算法还可以再进行时间的优化，将其化为n²算法。

实际上人数是一个无用条件，我们知道总的快乐牌数，那么人数一定会大于等于这个数。这种情况的所有必要条件就是：总的快乐牌num，限制牌堆m，那么可以化成以下情景：知道总的牌数num，问在限制每堆最大牌数为m时，堆成几堆牌能够使得快乐值最大。其方程式为：

dp[j]=max(dp[j],dp[j-i]+h[i]);请大家自行思考原因。

以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mac=5e2+10;

int h[mac];
ll dp[mac][mac];

int main()
{
    int n,m,s;
    int num=0;
    scanf ("%d%d%d",&n,&m,&s);
    for (int i=1; i<=n; i++){
        int x;
        scanf ("%d",&x);
        if (x==s) num++;
    }
    for (int i=1; i<=m; i++){
        int x;
        scanf ("%d",&x);
        h[i]=x;
    }
    for (int i=1; i<=n; i++){
        for (int j=1; j<=num; j++){
            for (int k=1; k<=min(j,m); k++){//枚举第i个人取k张牌 
                dp[i][j]=max(dp[i-1][j-k]+h[k],dp[i][j]);
            }
        }
    }
    printf ("%lld
",dp[n][num]);
    return 0;
}

View Code

以下是滚动数组优化的AC代码：

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mac=500+10;

int num=0,lim[mac];
ll dp[mac];

int main()
{
    int n,m,s;
    scanf ("%d%d%d",&n,&m,&s);
    for (int i=1; i<=n; i++){
        int x;
        scanf ("%d",&x);
        if (x==s) ++num;
    }
    for (int i=1; i<=m; i++){
        int x;
        scanf ("%d",&x);
        lim[i]=x;
    }
    for (int i=1; i<=n; i++){
        for (int j=num; j>=1; j--){
            for (int k=1; k<=min(m,j); k++){
                dp[j]=max(dp[j],dp[j-k]+lim[k]);
            }
        }
    }
    printf ("%lld
",dp[num]);
    return 0;
}

View Code

以下是n²的AC代码：

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mac=500+10;

int num=0,h[mac];
ll dp[mac];

int main()
{
    int n,m,s;
    scanf ("%d%d%d",&n,&m,&s);
    for (int i=1; i<=n; i++){
        int x;
        scanf ("%d",&x);
        if (x==s) ++num;
    }
    for (int i=1; i<=m; i++){
        int x;
        scanf ("%d",&x);
        h[i]=x;
    }
    for (int i=1; i<=m; i++){
        for (int j=i; j<=num; j++){
            dp[j]=max(dp[j],dp[j-i]+h[i]);
        }
    }
    printf ("%lld
",dp[num]);
    return 0;    
}

View Code

路漫漫兮