描述
度度熊擁有一個自己的Baidu空間，度度熊時不時會給空間朋友贈送禮物，以增加度度熊與朋友之間的友誼值。度度熊在偶然的機會下得到了兩種超級禮物，于是決定給每位朋友贈送一件超級禮物。不同類型的朋友在收到不同的禮物所能達到的開心值是不一樣的。開心值衡量標準是這樣的：每種超級禮物都擁有兩個屬性(A, B)，每個朋友也有兩種屬性(X, Y)，如果該朋友收到這個超級禮物，則這個朋友得到的開心值為A*X + B*Y。


由于擁有超級禮物的個數限制，度度熊很好奇如何分配這些超級禮物，才能使好友的開心值總和最大呢？


輸入
第一行n表示度度熊的好友個數。
接下來n行每行兩個整數表示度度熊好朋友的兩種屬性值Xi, Yi。
接下來2行，每行三個整數ki, Ai, Bi，表示度度熊擁有第i種超級禮物的個數以及兩個屬性值。
1 <= n <= 1000, 0 <= Xi, Yi, Ai, Bi <= 1000, 0 <= ki <= n, 保證k1+k2 >= n
輸出
輸出一行一個值表示好友開心值總和的最大值
樣例輸入
4
3 6
7 4
1 5
2 4
3 3 4
3 4 3
樣例輸出
118
提示

送給第一種禮物的人有1，3，4，送給第二種禮物的人有2

也可以看做背包問題的擴展，設對于朋友i,獲得禮物a的快樂是ai,獲得禮物b的快樂是bi,對于朋友i要判斷是放入a還是b

f[k1,k2] = max{ f[k1-1][k2]+ai,f[k1][k2]+bi }

#include <iostream> #include <stdio.h> #include <sstream> #include <cstring> #include <vector>using namespace std;class term { public:int x;int y;int a;int b;int k;//1 or 2 };int numa; int numb; int aa[2]; int bb[2]; vector<term> fd(1000); int f[1001][1001]; //vector<vector<vector<int> > > int main() {int n;scanf("%d",&n);for (int i=0;i<n;++i){int x,y;scanf("%d%d",&x,&y);fd[i].x = x;fd[i].y = y;}scanf("%d%d%d",&numa,&aa[0],&aa[1]);scanf("%d%d%d",&numb,&bb[0],&bb[1]);for (int i=0;i<n;++i){fd[i].a = fd[i].x * aa[0] + fd[i].y *aa[1];fd[i].b = fd[i].x *bb[0] + fd[i].y *bb[1];}memset(f,0,sizeof(f));for (int i=0;i<n;++i){for (int ai = numa;ai>=1;--ai){for (int bi = numb;bi>=1;--bi){int seleta = f[ai-1][bi] +fd[i].a;int seletb = f[ai][bi-1] +fd[i].b;f[ai][bi] = seleta>seletb?seleta :seletb;}}}cout<<f[numa][numb]<<endl;return 0; }

總結

以上是生活随笔為你收集整理的star3的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。