Codeforces Beta Round \ # 90 C 문제

       정말 오 랜 만 에 문 제 를 풀 었 습 니 다. 손 맛 도 없고 생각 도 무 뎌 졌 습 니 다. 두 전 을 앞 두 고 천천히 최상의 상 태 를 되 찾 아야 합 니 다.
       제목: m 과목 이 있 고 매 과목 은 최소 시간, 최대 시간, 난이도 계수 가 있 습 니 다.이 m 과목 에서 n 문 을 선택 하면 모든 과목 이 요구 하 는 범위 내 에서 시간 을 들 이 고 난이 도 는 절대적 으로 증가 하 는 동시에 현재 한 과목 이 전 과목 보다 k 배 나 많은 시간 을 들 여야 한다.가능 한 지, YES / NO, 가능 하 다 면 총 출력 시간 이 가장 많은 경우 (1 < = n < = m < = 50, 1 < = k < = 100, 1 < = a, b < 10 ^ 16 및 b - a < = 100).
       사고방식: a, b 범위 가 너무 넓 어서 직접 저장 할 수 없습니다.그러나 b - a < = 100, 그래서 2 차원 을 열 어 특정한 수업 에 걸 리 는 시간 을 나 타 낼 수 있 습 니 다.최종 적 으로 n 과목 을 해 야 하기 때문에 1 차원 은 현재 과정 이 몇 번 째 로 해 야 하 는 지 를 나타 낸다. dp [i] [j] [k] 는 현재 의 과정 j 가 선택 한 i 과목 이 고 j 의 최소 시간 보다 k 가 많다 는 것 을 나타 낸다.dp [i - 1] 에서 dp [i] 를 유도 할 수 있 고 전체 시간 이 가장 많 기 때문에 sum [i] [j] [k] 를 추가 하여 제 i 과목 에서 j 를 가장 많이 선택 한 다음 에 가장 좋 은 상황 을 선택 하면 된다.
       범 한 오류: 처음에 a, b 의 범 위 를 진지 하 게 보지 않 았 습 니 다. RE
                         그 다음 에 전체 시간 이 가장 많은 경 우 는 이때 보다 k 가 적은 선 택 이 존재 하고 나중에 k 배 (k = 1 시 에 따로 고려 해 야 한다) 라 고 생각 했다.그러나 이것 은 앞의 것 이 가장 크다 는 것 만 보장 하지만 앞의 것 과 가장 큰 것 은 보장 할 수 없다.여기 있 었 습 니 다.

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;

struct point//    
{
	__int64 n,a,b,c;//  ，    ，    ，    
}p[110];
struct po
{
	__int64 a,b;//     a，     p[a].a+b
}pre[51][51][110];
bool cmp(point a,point b)//         
{
	if(a.c!=b.c)
		return a.c<b.c;
	if(a.b!=b.b) 
		return a.b>b.b;
	return a.a>b.b;
}
__int64 dp[51][51][110];//dp[i][j][k]     i   j, p[j].a+k  
__int64 sum[51][51][110];//   i   j， p[j].a+k     

void DFS(__int64 n,__int64 i,__int64 j)
{
	if(n<=1)
	{
		printf("%I64d %I64d
",p[i].n,p[i].a+j);
		return;
	}
	DFS(n-1,pre[n][i][j].a,pre[n][i][j].b);
	printf("%I64d %I64d
",p[i].n,p[i].a+j);
}
int main()
{
	__int64 n,m,k,i,j,kk,ii,j1,a,b,c;
	while(scanf("%I64d%I64d%I64d",&n,&m,&k)!=EOF)
	{
		for(i=0;i<m;i++)
		{
			scanf("%I64d%I64d%I64d",&p[i].a,&p[i].b,&p[i].c);
			p[i].n=i+1;
		}
		
		memset(dp,0,sizeof(dp));
		memset(sum,0,sizeof(sum));
		sort(p,p+m,cmp);//     
		for(kk=1;kk<=n;kk++)
			for(i=0;i<m;i++)
			{
				for(j=0;j<=p[i].b-p[i].a;j++)
				{
					if(kk==1)
					{
						dp[kk][i][j]=p[i].c;
						sum[kk][i][j]=p[i].a+j;
						continue;
					}

					for(a=0,b=0,c=0,ii=0;ii<i;ii++)//       ii
					{
						if(p[ii].c==p[i].c) break;
						if(p[i].a+j-k>=p[ii].a&&p[i].a+j-k<=p[ii].b&&dp[kk-1][ii][p[i].a+j-k-p[ii].a])//      k
						{
							j1=p[i].a+j-k-p[ii].a;
							if(sum[kk-1][ii][j1]>c)
								a=ii,b=j1,c=sum[kk-1][ii][j1];
						}
						
						if((p[i].a+j)%k==0&&(p[i].a+j)/k>=p[ii].a&&(p[i].a+j)/k<=p[ii].b&&dp[kk-1][ii][(p[i].a+j)/k-p[ii].a])//      k 
						{
							j1=(p[i].a+j)/k-p[ii].a;
							if(sum[kk-1][ii][j1]>c)
								a=ii,b=j1,c=sum[kk-1][ii][j1];
						}

						if(c)//    
						{
							dp[kk][i][j]=p[i].c;
							pre[kk][i][j].a=a;
							pre[kk][i][j].b=b;
							sum[kk][i][j]=c+p[i].a+j;
						}
					}
				}
		}

		for(a=0,b=0,c=0,i=0;i<m;i++)//       
			for(j=0;p[i].a+j<=p[i].b;j++)
				if(dp[n][i][j])
				{
					if(sum[n][i][j]>c) 
						a=i,b=j,c=sum[n][i][j];
				}

		if(!c)
		{
			printf("NO
");
			continue;
		}
		printf("YES
");
		DFS(n,a,b);//    
	}
	return 0;
}