hdu 4362 (단조로운 대기열 최적화 dp)

제목: m단계가 있고, 단계마다 n개의 용구슬이 있으며, 어느 단계에서 하나의 용구슬을 선택하면 이 단계에서 다른 용구슬은 모두 사라진다.두 개의 m*n의 행렬을 제시한다. 첫 번째 행렬은 i단계 j개의 용구슬을 없애는 위치를 표시하고, 두 번째 행렬은 i단계 j개의 용구슬이 소모하는 에너지를 표시하며, 동시에 x번째 위치에서 두 번째 위치까지 | y-x|의 에너지를 소모해야 한다.마지막 단계마다 용구슬 하나를 가져가면 가장 적은 에너지 소모를 할 수 있다.
문제풀이 사고방식: dp[i][j]는 i단계에서 j번째 용구슬의 최소 소모 에너지를 선택한 것을 나타낸다.
전이 방정식: dp[i][j]=min{dp[i-1][k]+abs(loc[i][j]-loc[i-1][k])+cost[i][j]}, 여기에 매거해야 하는 것은 i, j, k이기 때문에 시간 복잡도 O(M*N*N)이다. 이 문제는 데이터가 빡빡하지 않은 것 같아서 운이 좋으면 AC할 수 있다.근데 정해는 아니야.
이곳은 단조로운 대열을 이용할 수 있다.dp[i][j]=min{dp[i-1][k]-loc[i-1][k]+loc[i][j]+cost[i][j]}(loc[i][j]>loc[i-1][k])) 때문에 dp[i-1][k]-loc[i-1][k]만 유지하면 됩니다.절대값이 있기 때문에 저는 두 개의 단조로운 대기열을 사용했습니다. 하나는 dp[i-1][k]-loc[i-1][k]를 유지하고 다른 하나는 dp[i-1][k]+loc[i-1][k]를 유지하지만 무슨 이유로WA를 사용했는지 모르겠습니다.
우선 여기에 놓고 나중에 생각이 나면 고치자.내 블로그를 지나가는 어떤 대신의 조언도 바랍니다.

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

const int maxn = 1005;
const int inf = 0x3f3f3f3f;
struct Node
{
	int pos,cost;
}mat[55][maxn];
int n,m,x;
int dp[55][maxn],q1[maxn],q2[maxn],h1,h2,t1,t2;

bool cmp(Node a,Node b)
{
	return a.pos < b.pos;
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&m,&n,&x);
		memset(dp,inf,sizeof(dp));
		for(int i = 1; i <= m; i++)
			for(int j = 1; j <= n; j++)
				scanf("%d",&mat[i][j].pos);
		for(int i = 1; i <= m; i++)
		{
			for(int j = 1; j <= n; j++)
				scanf("%d",&mat[i][j].cost);
			sort(mat[i]+1,mat[i]+1+n,cmp);<span style="white-space:pre">	</span>//           ，      
		}
		for(int i = 1; i <= n; i++)
			dp[1][i] = abs(x - mat[1][i].pos) + mat[1][i].cost;
		for(int i = 2; i <= m; i++)
		{
			h1 = h2 = t1 = t2 = 0;
			for(int j = 1; j <= n; j++)	// dp[i-1]            
			{
				while(h1 < t1 && dp[i-1][j] - mat[i-1][j].pos <= dp[i-1][q1[t1-1]] - mat[i-1][q1[t1-1]].pos) t1--;
				q1[t1++] = j;
				while(h2 < t2 && dp[i-1][j] + mat[i-1][j].pos <= dp[i-1][q2[t2-1]] + mat[i-1][q2[t2-1]].pos) t2--;
				q2[t2++] = j;
			}
			for(int j = 1; j <= n; j++)
			{
				while(h1 < t1 && mat[i][j].pos < mat[i-1][q1[h1]].pos) h1++;
				dp[i][j] = dp[i-1][q1[h1]] + mat[i][j].pos + mat[i][j].cost;
				while(h2 < t2 && mat[i][j].pos >= mat[i-1][q2[h2]].pos) h2++;
				dp[i][j] = min(dp[i][j],dp[i-1][q2[h2]] - mat[i][j].pos + mat[i][j].cost);
			}
		}
		int ans = inf;
		for(int i = 1; i <= n; i++)
			ans = min(ans,dp[m][i]);
		printf("%d
",ans);
	}
	return 0;
}

PS: 자세히 생각해 보니까 확실히 자신의 단조로운 대기열에 문제가 있다. 왜냐하면 내가 모든 dp[i-1]층을 대기열에 먼저 넣었기 때문에 문제가 발생할 수 있다. 내 뒤에 dp[i]층을 반복적으로 열거할 때 유효한 위치가 대기열에 없을 수도 있다.그래서 다른 사람의 코드를 참고했는데 dp[i][j]의 j를 먼저 열거해야 한다. 내가 먼저 j의 위치를 선택할 것을 보증한다. 이미 질서가 있기 때문에 mat[i][j]보다 크지 않다.pos 위치의 최소값은 된다. 같은 이치로 절대값이 있기 때문에 반대로 한 번 순환해야 한다.
자세한 절차는 코드를 참조하십시오.

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

const int maxn = 1005;
const int inf = 0x3f3f3f3f;
struct Node
{
	int pos,cost;
}mat[55][maxn];
int n,m,x;
int dp[55][maxn],q1[maxn],q2[maxn],h1,h2,t1,t2;

bool cmp(Node a,Node b)
{
	return a.pos < b.pos;
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&m,&n,&x);
		memset(dp,inf,sizeof(dp));
		for(int i = 1; i <= m; i++)
			for(int j = 1; j <= n; j++)
				scanf("%d",&mat[i][j].pos);
		for(int i = 1; i <= m; i++)
		{
			for(int j = 1; j <= n; j++)
				scanf("%d",&mat[i][j].cost);
			sort(mat[i]+1,mat[i]+1+n,cmp);
		}
		for(int i = 1; i <= n; i++)
			dp[1][i] = abs(x - mat[1][i].pos) + mat[1][i].cost;
		for(int i = 2; i <= m; i++)
		{
			int k = 1, Min = inf;
			for(int j = 1; j <= n; j++)
			{
				while(k <= n && mat[i][j].pos >= mat[i-1][k].pos)
				{
					Min = min(Min,dp[i-1][k] - mat[i-1][k].pos);
					k++;
				}
				dp[i][j] = Min + mat[i][j].pos + mat[i][j].cost;
			}
			k = n, Min = inf;
			for(int j = n; j >= 1; j--)
			{
				while(k >= 1 && mat[i][j].pos <= mat[i-1][k].pos)
				{
					Min = min(Min,dp[i-1][k] + mat[i-1][k].pos);
					k--;
				}
				dp[i][j] = min(dp[i][j],Min - mat[i][j].pos + mat[i][j].cost);
			}
		}
		int ans = inf;
		for(int i = 1; i <= n; i++)
			ans = min(ans,dp[m][i]);
		printf("%d
",ans);
	}
	return 0;
}