题目链接：http://acm.csust.edu.cn/problem/3028
Description
给你n个人，每一个人最多可以选k张牌，这n个人都喜欢数s，一张牌有一个数，如果这个数是s，则这个牌称为happy card
每一个人拿到不同数量的happy card 可以获得不同数量的欢乐值。
假如一个人拿到了 i 张happy card ，则可以获得 hi? 的欢乐值(hi?数组单调递增)， 没有happy card的人的欢乐值为0.
如果没有拿到happy card，则获得的欢乐值为0。
现在你需要把着n张牌分配给这n个人（每个人的牌数都可以为0），使这n个人的快乐值总和最大
Input
第一行三个数字1≤n≤500, 1≤k≤n , 1≤s≤1e9
接下来n个数代表n张牌上的数ai?， 1≤ai?≤1e9
接下来k个数代表hi?的值,1≤hi?≤1e9
保证 hi?≥hi−1?
Output
最大的快乐值和
Sample Input 1
5 3 2 2 2 2 2 2 2 6 7
Sample Output 1
14
Sample Input 2
4 3 9 9 9 9 9 1 2 3
Sample Output 2
4
一个DP题，对于萌新来讲可以有的难度。
列出所有条件：人数n，总的快乐牌num，限制手牌m
我们可以DP的是：前i个人在总牌数为j的情况下，第i个人拿k张牌的最大幸福值。想想似乎和01背包有点儿类似，那么状态转移方程也就不难写出来了：
dp[i][j]=max(dp[i-1][j-k]+h[k],dp[i][j]);当然我们的第一维其实可以直接滚动掉的。。
其实算法还可以再进行时间的优化，将其化为n2算法。
实际上人数是一个无用条件，我们知道总的快乐牌数，那么人数一定会大于等于这个数。这种情况的所有必要条件就是：总的快乐牌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\n",dp[n][num]); return 0; }
以下是滚动数组优化的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\n",dp[num]); return 0; }
以下是n2的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\n",dp[num]); return 0; }