우 객 망 [일 일 1 문제] 4 월 28 일 제목

링크:

    ：C/C++ 1 ，    2 
    ：C/C++ 32768K，    65536K
64bit IO Format: %lld

제목 설명
샤 오 밍 은 요리사 인 데 아침 에 일어나 면 하루 일 을 시작한다.그 가 있 는 식당 은 매일 아침 n 개의 식재 료 (각 식재 료 의 수량 은 무한 으로 볼 수 있다) 를 사 는데 샤 오 밍 은 식당 에 도착 할 때 부터 T 시간 동안 계속 일 했다.모든 요 리 를 만 드 는 데 는 특정한 식재 료 와 시간 이 필요 하지만 식재 료 를 오래 두 면 신선 하지 않 아 요리 의 맛 이 떨어진다.i 번 요 리 는 세 가지 속성 이 있 습 니 다. ai, bi, ci, ai 는 이 요리 의 맛 값 입 니 다. bi 는 이 요리 가 선택 한 재료 가 신선 하지 않 은 속도 입 니 다. 만약 에 t 시간 에 i 번 요 리 를 완성 하면 맛 있 는 값 은 ai - t * bi 입 니 다. 이 요 리 를 완성 하 는 데 ci 의 시간 이 필요 합 니 다.샤 오 밍 은 이 T 시간 안에 요 리 를 만들어 서 전체 맛 이 가장 크 기 를 원 하기 때문에 샤 오 밍 이 너 에 게 도움 을 청 했다.
입력 설명:
첫 번 째 줄 은 세 개의 정수 n, m, T 를 입력 하여 각각 식재 료 종류, 요리 종류 와 근무 시간 을 대표 한다.두 번 째 줄 에 n 개의 정수 bi 를 입력 하면 i 번 째 식재 료 가 신선 하지 않 은 속 도 를 나타 낸다.3 - n + 2 줄 은 줄 마다 세 개의 정수 j, ai, ci 를 입력 하여 각각 i 번 요리 에 필요 한 식재 료 번호, 요리 의 맛 값, 완성 시간 을 대표 합 니 다.데이터 보증: 0
출력 설명:
한 줄, 한 정 수 를 출력 하여 최대 총 맛 치 를 표시 합 니 다.
예제 1 입력 복사

1 1 74
2
1 502 47

출력 복사

408

예제 2 입력 복사

2 2 10
2 1
1 100 8
2 50 3

출력 복사

84

비고: 최대 총 맛 치 는 마이너스 일 수 있 습 니 다.
문제 풀이:
문 제 를 본 첫 번 째 반응 은 비 성 가 비 였 다 (최근 에 한 문 제 를 풀 었 다). 바로 하나의 평가 기준 을 만 든 다음 에 순 위 를 정 하여 두 가지 요 리 를 계산 하고 x 와 y 를 먼저 만들어 맛 값 을 보 는 것 이다. 먼저 x 를 한 다음 y: a [x] - (sum + t [x]) ∗ b [x] + a [y] - (sum + t [x] + t [x] + t [y]) ∗ b [y] (1) 먼저 y [y] - (y] - (sum + t [y]]] - (sum + t [y]]]]]]] - (sum + + t [y]]] [y]]]]] [y]]] (1) 먼저 y 후 x: a [y] - (sum+ t [y]) ∗ b [x] (2)sum 은 이전에 만 든 요리 에 사용 되 는 시간 입 니 다. 우 리 는 어느 순서 가 가장 좋 은 지 알 아야 합 니 다. 두 가 지 를 비교 해 야 합 니 다. 만약 에 먼저 x 후 y 가 가장 좋 고 식 1 > 식 2 를 간소화 하면 tx / bx tx * by < ty * bx 를 얻 을 수 있 습 니 다. 그리고 우 리 는 dp 로 만 들 수 있 습 니 다. 01 가방, dp [i] 는 각 시간 t 의 완벽 한 맛 값 상황 을 나타 내 는 구조 체, edge [] a 맛 값, b 신선 하지 않 은 속도, c 시간, j 순서 입 니 다.
dp[j]=max(dp[j],dp[j-edge[i].c]+edge[i].a-j*edge[edge[i].j].b);
dp [j - edge [i]. c] + edge [i]. a - jedge [edge [i]. j]. b 의 첫 번 째 dp 는 이 요 리 를 만 들 기 전에 얻 은 맛 있 는 가 치 를 나타 낸다.

#include
typedef long long ll;
using namespace std;
const int inf=-1e9-2;
const int maxn=2e5+8;
ll sum=inf;//         
int n,m,t;
ll dp[maxn];
struct node{
     
	ll j,a,b,c;
}edge[maxn];
//bool max(int x,int y)
//{
     
//	return x
//}
bool cmp(node x,node y)
{
     
	return x.c*edge[y.j].b<y.c*edge[x.j].b;
}
int main()
{
     
	scanf("%lld%lld%lld",&n,&m,&t);
	for(int i=1;i<=n;i++)scanf("%lld",&edge[i].b);
	for(int i=1;i<=m;i++)scanf("%lld%lld%lld",&edge[i].j,&edge[i].a,&edge[i].c);
	
	sort(edge+1,edge+1+m,cmp);
//	
//	for(int i=1;i<=m;i++)
//	{
     
//		cout<
//	}
	for(int i=1;i<=t;i++)dp[i]=inf;//dp     
	
	for(int i=1;i<=m;i++)
	for(int j=t;j>=edge[i].c;j--)
	{
     
		ll w= dp[j-edge[i].c]+ edge[i].a - j * edge[i].b;
//		printf("%lld %lld %lld
 ",dp[j-edge[i].c],edge[i].a,j * edge[i].b);
		dp[j]=max( dp[j] , dp[j-edge[i].c]+edge[i].a-j * edge[i].b);
//		printf("w=%lld,dp[%d]=%lld
",w,j,dp[j]);
	 } 
	 for(int i=1;i<=t;i++)sum=max(sum,dp[i]);
	 cout<<sum<<endl;
	 return 0;
} 
/*
2 2 10
2 1
1 100 8
2 50 3
*/
/*
100 2 8
50 1 3
*/