JZOJ4693. 【NOIP2016提高A組模擬8.14】瘋狂的火神

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

Description
火神為了檢驗zone的力量,他決定單挑n個人。
由於火神訓練時間有限,最多隻有t分鐘,所以他可以選擇一部分人來單挑,由於有麗子的幫助,他得到了每個人特定的價值,每個人的價值由一個三元組(a,b,c)組成,表示如果火神在第x分鐘單挑這個人(x指單挑完這個人的時間),他就會得到a-b*x的經驗值,並且他需要c分鐘來打倒這個人。
現在火神想知道,他最多可以得到多少經驗值,由於火神本來就很笨,進入zone的瘋狂的火神就更笨了,所以他希望你來幫他計算出他最多可以得到多少經驗值。

Input
第一行一個正整數T,表示資料組數
對於每組資料,第一行為兩個正整數n和t,表示跟火神單挑的人的個數和火神的訓練時間。
下面n行,每行三個正整數Ai,Bi,Ci,表示每個人的價值,含義見題目。
Output
對於每組資料輸出一行一個整數表示火神最多能得到多少經驗值

Sample Input
1
4 10
110 5 9
30 2 1
80 4 8
50 3 2
Sample Output
88

Data Constraint
對於 20%的資料1≤n≤10
對於50%的資料1≤n≤18
對於100%的資料1≤n≤1000,1≤t≤3000,1≤Ci≤t,Ai≤10^6
保證n>200的資料組數不超過五組,其他的資料組數不超過10組
保證每個人貢獻的經驗值到訓練結束都不會變成負數

分析

看到題目就感覺像01揹包,

在有限的時間裡面,挑戰一些人,使得獲得的經驗值最大。

但是,挑戰每個人獲得的經驗值與時間相關。

那麼如果確定了挑戰的順序,

剩下的東西就可以通過01揹包輕鬆搞定。

  • 但是,這個順序怎麼求?

如果求全排列,那麼時間複雜度就是階乘了,

很顯然,會超時。

那麼,可能會有一種最優順序了。

假設我們選擇了第i個人和第j個人,

  • 怎樣給題目安排順序呢?

再假設在第m個時刻,第i個人排在第j個人前更優

就有:

ai−bi∗(ci m) aj−bj∗(ci cj m)>ai−bi∗(ci cj m) aj−bj∗(ci m)a_i-b_i*(c_i m) a_j-b_j*(c_i c_j m)>a_i-b_i*(c_i c_j m) a_j-b_j*(c_i m)

化簡得:

bj∗ci<bi∗cjb_j*c_i<b_i*c_j

再移項:

bj÷bi<cj÷cib_j÷b_i<c_j÷c_i

現在我們就得到一個排序的條件。

  • 換一個方面想,也很容易理解。

挑戰兩個人可以獲得的經驗值就是ai aja_i a_j

因為在時刻m

所以都要減去 m∗bi m∗bjm*b_i m*b_j

而剩下的影響就是順序了,

很顯然,就是上面的那道式子。

接下來就很簡單了,

只需要做一次01揹包就可以了。

code(c )

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#include <stdlib.h>
#include <math.h>
#define a(i) g[i].a
#define b(i) g[i].b
#define c(i) g[i].c
using namespace std;
struct note{
int a,b,c;
}g[1001];
int T,n,t,ans; 
int f[3003];
bool cmp(note x,note y)
{
return(y.b*x.c<x.b*y.c);
}
int main()
{
scanf("%d",&T);
while(T)
{
T--;
scanf("%d%d",&n,&t);
for(int i=1;i<=n;i  )
scanf("%d%d%d",&a(i),&b(i),&c(i));
sort(g 1,g 1 n,cmp);
memset(f,0,sizeof(f));
for(int i=1;i<=n;i  )
for(int j=t;j>=c(i);j--)
f[j]=max(f[j],f[j-c(i)] a(i)-b(i)*j);
ans=0;
for(int i=1;i<=t;i  )
ans=max(ans,f[i]);
printf("%d\n",ans);
}
}

相關文章

程式語言 最新文章