poj 3257(해시+2차원dp)

제목: 1-L의 롤러코스터를 연결하여 n단에서 선택할 수 있는 건설 방안을 제시해야 한다.단락마다 시작 위치, 끝 위치, 대가, 즐거움 정도가 있다.1-L의 길이를 실현하려면 서로 인접한 양쪽이 처음과 끝이 연결되어야 하며 총 건설 대가는 B 안에서 통제해야 하며 최대 얼마나 많은 즐거움을 얻을 수 있는지 물어야 한다.
문제풀이 사고방식: 여기에 두 가지 제한 조건이 있는데 L과 B이다. 첫 번째 사고방식은 dp[i][j][k]가 앞의 i단을 나타낼 수 있고 수련의 길이는 j이고 비용은 k의 최대 가치이다.그러나 데이터량에 따라 시간 초과가 틀림없다.여기도 마찬가지로 꼼꼼하게 발굴해야 한다. 서로 인접한 두 끝은 처음과 끝이 연결되어야 하기 때문에 대응하는 길이가 L이다. 반드시 한 단락의 실제 위치가 L과 같아야 한다. 그러면 우리는 각 단락의 첫 번째 주소를 하히로 저장할 수 있다. 그때 일일이 L을 들면 하히리에서 직접 꺼내면 모든 단락의 순환이 줄어든다.dp[i][j]는 수리의 길이가 i이고 비용이 j의 최대 가치임을 나타낸다.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 10005;
struct Node
{
	int start,end,len,cost,fun;
}roller[maxn];
struct HashNode
{
	int id,next;
}HNode[maxn];
int L,N,B,dp[1005][1005]; //dp[i][j]        i，   j    
int h[maxn],cnt;

bool cmp(Node a,Node b)
{
	if(a.start == b.start) return a.end < b.end;
	return a.start < b.start;
}

void add(int len,int id)
{
	HNode[cnt].id = id, HNode[cnt].next = h[len];
	h[len] = cnt++;
}

int main()
{
	while(scanf("%d%d%d",&L,&N,&B)!=EOF)
	{
		memset(h,-1,sizeof(h));
		memset(dp,-1,sizeof(dp));
		for(int i = 1; i <= N; i++)
		{
			scanf("%d%d%d%d",&roller[i].start,&roller[i].len,&roller[i].fun,&roller[i].cost);
			roller[i].end = roller[i].start + roller[i].len;
		}
		dp[0][0] = 0;
		for(int i = 1; i <= N; i++)
			add(roller[i].start,i);	//      
		for(int i = 0; i <= L; i++)
			for(int j = 0; j <= B; j++)
			{
				if(dp[i][j] == -1) continue;
				int t = h[i];
				while(t != -1)
				{
					if(roller[HNode[t].id].cost + j <= B)
						dp[roller[HNode[t].id].end][j + roller[HNode[t].id].cost] = max(dp[roller[HNode[t].id].end][j+roller[HNode[t].id].cost],dp[i][j]+roller[HNode[t].id].fun);
					t = HNode[t].next;
				}
			}
		int ans = -1;
		for(int i = 0; i <= B; i++)
			ans = max(ans,dp[L][i]);
		printf("%d
",ans);
	}
	return 0;
}