[01背包]vijos1013 找啊找啊找GF

P1013 找啊找啊找GF 時間: 1000ms / 空間: 131072KiB / Java類名: Main

背景

MM七夕模拟賽

描述

"找啊找啊找GF,找到一個好GF,吃頓飯啊拉拉手,你是我的好GF.再見."

"诶,别再見啊..."

七夕...七夕...七夕這個日子,對于sqybi這種單身的菜鳥來說是多麼的痛苦...雖然他聽着這首叫做"找啊找啊找GF"的歌,他還是很痛苦.為了避免這種痛苦,sqybi決定要給自己找點事情幹.他去找到了七夕模拟賽的負責人zmc MM,讓她給自己一個出題的任務.經過幾天的死纏爛打,zmc MM終于同意了.

但是,拿到這個任務的sqybi發現,原來出題比單身更讓人感到無聊-_-....是以,他決定了,要在出題的同時去辦另一件能夠使自己不無聊的事情--給自己找GF.

sqybi現在看中了n個MM,我們不妨把她們編号1到n.請MM吃飯是要花錢的,我們假設請i号MM吃飯要花rmb[i]塊大洋.而希望騙MM當自己GF是要費人品的,我們假設請第i号MM吃飯試圖讓她當自己GF的行為(不妨稱作泡該MM)要耗費rp[i]的人品.而對于每一個MM來說,sqybi都有一個對應的搞定她的時間,對于第i個MM來說叫做time[i]. sqybi保證自己有足夠的魅力用time[i]的時間搞定第i個MM^_^.

sqybi希望搞到盡量多的MM當自己的GF,這點是毋庸置疑的.但他不希望為此花費太多的時間(畢竟七夕賽的題目還沒出),是以他希望在保證搞到MM數量最多的情況下花費的總時間最少.

sqybi現在有m塊大洋,他也通過一段時間的努力攢到了r的人品(這次為模拟賽出題也攢rp哦~~).他憑借這些大洋和人品可以泡到一些MM.他想知道,自己泡到最多的MM花費的最少時間是多少.

注意sqybi在一個時刻隻能去泡一個MM--如果同時泡兩個或以上的MM的話,她們會打起來的...

輸入格式

輸入的第一行是n,表示sqybi看中的MM數量.接下來有n行,依次表示編号為1, 2, 3, ..., n的一個MM的資訊.每行表示一個MM的資訊,有三個整數:rmb, rp和time.最後一行有兩個整數,分别為m和r.

輸出格式

你隻需要輸出一行,其中有一個整數,表示sqybi在保證MM數量的情況下花費的最少總時間是多少.

測試樣例1

輸入

4 

1 2 5 

2 1 6 

2 2 2 

2 2 3 

5 5

輸出

13

備注

資料規模

對于20%資料,1<=n<=10;

對于100%資料,1<=rmb<=100,1<=rp<=100,1<=time<=1000;

對于100%資料,1<=m<=100,1<=r<=100,1<=n<=100.

Hint

sqybi說:如果題目裡說的都是真的就好了...

sqybi還說,如果他沒有能力泡到任何一個MM,那麼他就不消耗時間了(也就是消耗的時間為0),他要用這些時間出七夕比賽的題來攢rp...

出題人

sqybi GG 思路：

兩個狀态，兩個狀态轉移方程，其本質還是01背包

動态轉移方程：f[j][k] = max{f[j-m[i]][k-r[i]] + 1} (j >= m[i] && k >= r[i]);

  g[j][k] = min{g[j-m[i]][k-r[i]] + t[i]};

原始的01背包決策隻有兩個：放與不放；本題來說就是對于一個人泡與不泡的問題；

f[j][k] 代表前 i 個姑娘花 j 錢 k 人品所能得的最多GF，i 由循環展現；

g[j][k] 記錄對應 f[j][k] 中花 j 錢 k 人品所能得的最多GF所花費的最少時間

代碼：

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
//f[j][k]= f[j-m[i]][k-r[i]]+1 (j>=m[i] && k>=r[i]);
//決策隻有兩個：放與不放，本題就是泡與不泡的問題
const int N = 110;
const int M = 1100;
#define inf 1<<29
int f[N][N];//f[j][k] 代表花j錢花k人品所得的最多的GF
int g[N][N];//對應f記錄花費時間
int m[N];//錢
int r[N];//人品
int t[N];//時間
int main()
{
    int n, money, rp;
    int i, j, k;

    scanf("%d", &n);
    for(i = 1; i <= n; i++)
        scanf("%d%d%d", &m[i], &r[i], &t[i]);
    scanf("%d%d", &money, &rp);
    for(i = 1; i <= n; i++)
        for(j = money; j >= m[i]; j--)
            for(k = rp; k >= r[i]; k--)
            {
                if(f[j][k] < f[j-m[i]][k-r[i]] + 1)
                {
                    f[j][k] = f[j-m[i]][k-r[i]] + 1;
                    g[j][k] = g[j-m[i]][k-r[i]] + t[i];
                }
                else if(f[j][k] == f[j-m[i]][k-r[i]] + 1)
                    g[j][k] = min(g[j][k], g[j-m[i]][k-r[i]] + t[i]);
            }
    printf("%d", g[money][rp]);

    return 0;
}
/*
4
1 2 5
2 1 6
2 2 2
2 2 3
5 5
------
13
*/
           

反思：

貼上之前的錯誤代碼：

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
//f[i][j][k] = max{f[i-1][j][k], f[i-1][j-m[i]][k-r[i]]+t[i]}
const int N = 110;
#define inf 1<<29
int f[N][N][N];//f[i][j][k] 代表前i個姑娘花j錢花r人品所花費的最少時間
int m[N];//錢
int r[N];//人品
int t[N];//時間
int main()
{
    int time, money, rp;
    int i, j, k;

    scanf("%d", &time);
    for(i = 0; i <= time; i++)
        for(j = 0; j <= time; j++)
            for(k = 0; k <= time; k++)
                f[i][j][k] = inf;
    for(i = 1; i <= time; i++)
        scanf("%d%d%d", &m[i], &r[i], &t[i]);
    scanf("%d%d", &money, &rp);
    for(i = 1; i <= time; i++)
        for(j = 1; j <= money; j++)
            for(k = 1; k <= rp; k++)
            {
                if(j >= m[i] && k >= r[i])
                    f[i][j][k] = min(f[i-1][j][k], f[i-1][j-m[i]][k-r[i]] + t[i]);
                else
                    f[i][j][k] = f[i-1][j][k];
            }
    printf("%d", f[time][money][rp]);

    return 0;
}
           

這個代碼我是用的三維數組 f[i][j][k] 其實和上面的AC代碼 f[j][k] 一種形式，f[j][k]的i用循環來展現了，是一種優化，但其代表的意思不同；

錯誤代碼中 f[i][j][k] 代表前 i 個姑娘花 j 錢 k 人品所花費的最少時間；

AC代碼中f[k][k] 代表前 i 個姑娘花 j 錢 k 人品所能得的最多GF，然後用開 g[j][k] 來儲存保證GF數量前提下的最少時間；

思路但缺乏靈活性，不會拐彎，要更奇思妙想一點！