【問題描述】
你得到了一個龍珠雷達，它會告訴你龍珠出現的時間和地點。
龍珠雷達的畫面是一條水準的數軸，每一個視窗時間，數軸的某些點上會出現同一種龍珠，每當你獲得其中一顆龍珠，其它龍珠就會消失。下一個視窗時間，數軸上又會出現另一種龍珠。總共有n個視窗時間，也就是總共有n種龍珠。
假設你會瞬間移動，你從數軸的x點移動到y點，耗時0秒，但是需要耗費|x-y|的體力。同時，挖出一顆龍珠也需要耗費一定的體力。請問，最少耗費多少體力，就可以收集齊所有種類的龍珠。
【輸入格式】
第一行，三個整數n,m,x,表示共有n個視窗時間，每個視窗時間會出現m個龍珠，x是一開始你所處的位置。
接下來有兩個n*m的矩陣。
對于第一個矩陣，坐标為(i,j)的數字表示第i個視窗時間，第j個龍珠的位置。
對于第二個矩陣，坐标為(i,j)的數字表示第i個視窗時間，挖取第j個龍珠所需的體力。
【輸出格式】
一個整數，表示所需最小體力
【輸入樣例】
3 2 5
2 3
4 1
1 3
1 1
1 3
4 2
【輸出樣例】
8
【資料範圍】
所有資料均為整數
數軸範圍在0到30000
挖一顆龍珠所需體力不超過30000
結果保證在int範圍
對于50%的資料，1<=n<=50,1<=m<=500。
對于100%的資料，1<=n<=50,1<=m<=5000。
不難分析出動态規劃方程：
設結構體：a[i][j].x=表示第 i 個時間視窗出現的第 j 個龍珠的位置。
：a[i][j].c=表示第 i 個時間視窗挖第 j 個龍珠需要耗費的體力。
//f(i,j)表示在第i個視窗拾取第j個龍珠後所耗費的最小體力
//f(i,j)=min（f(i-1,k)+abs(a[i-1][k].wz-a[i][j].wz) || 1<=k<=m ）+a[i][j].c
邊界：
f(1,j)= |a[1][j].x-x0|+ a[1][j].c //在第 1 個時間視窗收集第 j 個龍珠需要的體力
純粹dp：
solve50（）
for(int j=;j<=m;j++)
f[][j]=abs(a[][j].wz-p)+a[][j].c;
//f(i,j)表示在第i個視窗拾取第j個龍珠後所耗費的最小體力
//f(i,j)=min（ f(i-1,k)+abs(p[i-1][k].wz-p[i][j].wz) || 1<=k<=m ）+p[i][j].c
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
ans=inf;
for(int k=;k<=m;k++)
{
rr=f[i-][k]+abs(a[i-][k].wz-a[i][j].wz);
ans=min(ans,rr);
}
f[i][j]=ans+a[i][j].c;
}
}
ans=inf;
for(int i=;i<=m;i++)
ans=min(ans,f[n][i]);
printf("%d",ans);
加入單調隊列優化（偷個懶，因為這個滑動視窗左端固定，不用記錄下标，隻找最小值）：
solve100（）
for(int i=;i<=n;i++)
{
int k=;
int minv=inf;
//when（p[i][j].wz>=p[i-][k].wz）
//f(i,j)=min（f(i-,k)-p[i-][k].wz) || <=k<=m ）+p[i][j].c+p[i][j].wz
for(int j=;j<=m;j++)
{
while(k<=m && a[i][j].wz>=a[i-][k].wz)
{
t=f[i-][k]-a[i-][k].wz;
minv=min(minv,t);
k++;
}
f[i][j]=minv+a[i][j].c+a[i][j].wz;
}
k=m,minv=inf;
//when（p[i][j].wz<p[i-][k].wz）
//f(i,j)=min（f(i-,k)+p[i-][k].wz) || <=k<=m ）+p[i][j].c-p[i][j].wz
for(int j=m;j>=1;j--)
{
while(k>= && a[i][j].wz<a[i-][k].wz)
{
t=f[i-][k]+a[i-][k].wz;
minv=min(minv,t);
k--;
}
f[i][j]=min(f[i][j],minv+a[i][j].c-a[i][j].wz);
}
}
ans=inf;
for(int i=;i<=m;i++)
ans=min(ans,f[n][i]);
printf("%d",ans);