Test Message

c269: 裴裴與女生們

內容

裴裴剛上大學，決定來認識一些女生。校園裡有 n 個女生，分別編號為 1~n，她們都有一個共同的特性，就是如果你花 si的時間陪伴她，她就會滿足，你就會從她身上得到 vi的好感度，但花超過 si的時間陪她也不會得到額外的好感度。

但是經過裴裴的精心研究發現，這些女生可以細分為兩種類型。第一種類型的女生有一個特性，就是她們回饋你的好感度正比於你陪他們的時間。也就是如果第 i 個女生是第一類的女生，你花 si/k 的時間陪她，就會得到 vi/k 的好感度。第二種類型的女生就比較麻煩了，除非你讓他滿足(也就是花 si的時間陪她)，不然你是不會得到任何好感度的。裴裴很忙，他只有 T 單位的時間可以拿來陪女生，請算出裴裴最多可以得到多少好感度?為了方便輸出，請自動將答案四捨五入至整數位。

例如:

有 4 個女生資料分別為下，且裴裴有 10 單位的時間

編號 1:s1=5,v1=15,第二類

編號 2:s2=5,v2=14,第二類

編號 3:s3=4,v1=13,第二類

編號 4:s4=8,v2=17,第二類

裴裴的最佳策略是花 5 單位的時間陪伴編號 1 的女生以及 5 單位的時間陪伴編號 2 的女生，如此可得到最多的好感度 15+14=29.

若編號 4 的女生改為第一類，則最佳策略是花 5 單位的時間陪伴編號 1 的女生,4 單位的時間陪伴編號 3 的女生，以及 1 單位的時間陪伴編號 4 的女生，如此可得到最多的好感度 15+13+17/8=30.125.(四捨五入後為 30)

輸入

測資的第一行有兩個整數 n,T 分別代表有幾個女生以及裴裴有多少單位的時間。接下來 n 行中每行有 3 個數字 si,vi,pi描述這個女生。如果裴裴花 si的時間陪伴她，她就會滿足，裴裴就會從她身上得到 vi的好感度，且這個女生是屬於第 pi類的女生。

(1≦n≦10000,1≦T,si≦1000,1≦vi≦109,pi=1 或 2)

//sample output 1
29
//sample output 2
30

輸出

對於每一筆測資，請輸出一個數字代表裴裴能獲得的最大好感度。輸出的數字請四捨五入到整數。

//sample input 1
4 10
5 15 2
5 14 2
4 13 2
8 17 2
//sample input 2
4 10
5 15 2
5 14 2
4 13 2
8 17 1

解題思路

背包問題的變種，如果只看第二類女生其實就是單純的背包問題。

而既然已經知道第二類女生的解決方案，那就想辦法將第一類女生轉換成第二類來計算。

已經知道第一類女生即使只陪她一單位時間也能拿到對應比例的好感度，那把該女生切成 n 個 1 單位時間來計算結果也會是一樣的，如此一來，第一類女生時間為 s、好感度為 v，就能將她看做

s 個 "si = 1 , vi = v/s , p = 2"的女生

Ex: "si = 5 , vi = 10 , p = 1" 就可以看作 5 個 "si = 1 , vi = 2 , p = 2" 的女生。
可以把第一類女生轉化成第二類之後，剩下就是經典的背包問題了。

注意！第一類女生轉第二類女生時好感度會用到除法且不保證整除。

完整程式碼

AC (20ms, 112KB)
#include <stdio.h>

unsigned long long favor[1010];

int main()
{
    unsigned long long  gFavor;
    int girls, times, gTime, gType;
    char flag;
    scanf(" %d %d", &girls, &times);
    for (int h = 0; h < girls; h++)
    {
        scanf("%d %llu %d", &gTime, &gFavor, &gType);
        gFavor *= 100000;
        if (gType == 1)
        {
            gFavor = gFavor / gTime;
            do
            {
                flag = 0;
                for (int i = times; i >= 1; i--)
                {
                    if (favor[i - 1] + gFavor > favor[i])
                    {
                        favor[i] = favor[i - 1] + gFavor;
                        flag = 1;
                    }
                }
            } while (--gTime && flag);
        }
        else
        {
            for (int i = times; i >= gTime; i--)
            {
                if (favor[i - gTime] + gFavor > favor[i])
                    favor[i] = favor[i - gTime] + gFavor;
            }
        }
    }
    printf("%llu\n", (favor[times] + 50000) / 100000);
    return 0;
}