HDU 4362

方程很简单

p[i][j] = min{dp[i-1][k] + |pos[i-1][k] - pos[i][k]|} + v[i][j];

循环求值肯定TLE，主要是绝对值不方便。好吧，我真的BI了狗了，竟然想不到怎么样去绝对值。F，只要从左到右dp一次，再从右往左dp一次，不就好了吗？？？？？F。当然了，必须是选按位置排序。开始用单调队列，后来发现根本没必要了。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
struct Node{
	int pos,val;
};
const int inf=1<<30;
Node map[55][1050];
bool cmp(Node a,Node b){
	if(a.pos<b.pos) return true;
	return false;
}
int que[1050];
int dp[55][1050];


int main(){
	int T,n,m,x;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&m,&n,&x);
		for(int i=1;i<=m;i++){
			for(int j=1;j<=n;j++){
				scanf("%d",&map[i][j].pos);
			}
		}
		for(int i=1;i<=m;i++){
			for(int j=1;j<=n;j++){
				scanf("%d",&map[i][j].val);
			}
			sort(map[i]+1,map[i]+1+n,cmp);
		}
		for(int i=1;i<=n;i++){
			dp[1][i]=abs(map[1][i].pos-x)+map[1][i].val;
		}
		int k,mm;
		for(int i=2;i<=m;i++){
			mm=inf;
			k=1;
			for(int j=1;j<=n;j++){
				for(k;k<=n;k++){
					if(map[i-1][k].pos>map[i][j].pos) break;
					mm=min(mm,dp[i-1][k]-map[i-1][k].pos);
				}
				dp[i][j]=mm+map[i][j].pos+map[i][j].val;
			}
			k=n;
			mm=inf;
			for(int j=n;j>=1;j--){
				for(k;k>=1;k--){
					if(map[i-1][k].pos<map[i][j].pos) break;
					mm=min(mm,dp[i-1][k]+map[i-1][k].pos);
				}
				dp[i][j]=min(dp[i][j],mm-map[i][j].pos+map[i][j].val);
			}
		}
		int ans=inf;
		for(int i=1;i<=n;i++)
		ans=min(dp[m][i],ans);
		printf("%d
",ans);
	}
	return 0;
}