【问题描述】
你得到了一个龙珠雷达，它会告诉你龙珠出现的时间和地点。
龙珠雷达的画面是一条水平的数轴，每一个窗口时间，数轴的某些点上会出现同一种龙珠，每当你获得其中一颗龙珠，其它龙珠就会消失。下一个窗口时间，数轴上又会出现另一种龙珠。总共有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=1;j<=m;j++) f[1][j]=abs(a[1][j].wz-p)+a[1][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=2;i<=n;i++) { for(int j=1;j<=m;j++) { ans=inf; for(int k=1;k<=m;k++) { rr=f[i-1][k]+abs(a[i-1][k].wz-a[i][j].wz); ans=min(ans,rr); } f[i][j]=ans+a[i][j].c; } } ans=inf; for(int i=1;i<=m;i++) ans=min(ans,f[n][i]); printf("%d",ans);加入单调队列优化（偷个懒，因为这个滑动窗口左端固定，不用记录下标，只找最小值）：
solve100（） for(int i=2;i<=n;i++) { int k=1; int minv=inf; //when（p[i][j].wz>=p[i-1][k].wz） //f(i,j)=min（f(i-1,k)-p[i-1][k].wz) || 1<=k<=m ）+p[i][j].c+p[i][j].wz for(int j=1;j<=m;j++) { while(k<=m && a[i][j].wz>=a[i-1][k].wz) { t=f[i-1][k]-a[i-1][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-1][k].wz） //f(i,j)=min（f(i-1,k)+p[i-1][k].wz) || 1<=k<=m ）+p[i][j].c-p[i][j].wz for(int j=m;j>=1;j--) { while(k>=1 && a[i][j].wz<a[i-1][k].wz) { t=f[i-1][k]+a[i-1][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=1;i<=m;i++) ans=min(ans,f[n][i]); printf("%d",ans);