JZOJ 4693. [NOIP 2016 A 조 시 뮬 레이 션 8.14 증가] 광기 의 화신

설명 화신 은 zone 의 힘 을 검증 하기 위해 n 명 을 뽑 기로 했다.화신 의 훈련 시간 이 제한 되 어 있 고 최대 t 분 밖 에 안 되 기 때문에 그 는 일 부 를 선택 하여 한판 붙 을 수 있다. 려 자의 도움 으로 그 는 모든 사람의 특정한 가 치 를 얻 었 다. 모든 사람의 가 치 는 하나의 3 원 조 (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 의 데이터 조 수 는 5 조 를 초과 하지 않 으 며, 기타 데이터 조 수 는 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)
간단하게:
bj∗ci＜bi∗cj
다시 항목 이동:
bj÷bi＜cj÷ci
지금 우 리 는 정렬 의 조건 을 얻 을 수 있다.

다른 한편 으로 는 이해 하기 쉽다.

두 사람 이 획득 할 수 있 는 경험 치 를 도전 하면 ai + aj 입 니 다.
시간
그래서 m ∗ bi + m ∗ bj 를 빼 야 돼 요.
남 은 영향 은 순서 다.
분명히 위의 그 식 이다.
이제 간단 해..
01 백 팩 을 한 번 만 만 들 면 됩 니 다.
code(c++)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#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.cint 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
",ans);
    }
}