题目大意,有n*m（n<=m<=300）的格子，有p个宝箱，现在你在（1,1）拥有种类1宝箱的钥匙,当你打开k号宝箱时会得到k+1号宝箱的钥匙,第p种宝箱有且只有一个,问至少要走多少步才能得到第p宝箱。
首先并没与什么套路可循,只有硬着头皮dp一波,心想暴力绝对超时（好吧，打脸了）,我的做法是dp，不难定义出这样的状态dp[i][j]表示走到(i,j)的最小路程,就会得到这样的转移方程
dp[i][j] = dp[lasti][lastj]+|lasti-i|+|lastj-j| && d[lasti][lastj]+1 = d[i][j]那么这样的复杂度就是n^2*m^2.
我们再将式子打开,dp[i][j] = (dp[lasti][lastj]+lasti+lastj)-i-j 暂时不考虑符号问题,我们会得到只关于(lasti,lastj)的式子,那么我们就可以通过树状数组来优化区间.
得到转移方程:
dp[i][j] = Min(dp[lasti][lastj]-lasti-lastj)+i+j//从左上转移而来
dp[i][j] = Min(dp[lasti][lastj]+lasti-lastj)-i+j// 左下
dp[i][j] = Min(dp[lasti][lastj]+lasti+lastj)-i-j// 右下
dp[i][j] = Min(dp[lasti][lastj]-lasti+lastj)+i-j// 右上
4个树状数组去维护，m*n*logm*logn
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#define lowbit(i) i&-i
using namespace std;
const int maxn = 310;
#define clr(a,b) memset(a,b,sizeof(a))
/*
dp[i][j] = (dp[lasti][lastj]-lasti-lastj)+i+j;0
dp[i][j] = (dp[lasti][lastj]-lasti+lastj)+i-j;1
dp[i][j] = (dp[lasti][lastj]+lasti+lastj)-i-j;2
dp[i][j] = (dp[lasti][lastj]+lasti-lastj)-i+j;3
*/
const int inf = (1<<30);
struct node{int x,y;};
vector <node>gap[maxn*maxn];
int dp[maxn][maxn];
int n,m,p;
struct BIT{
int a,b;
int c[maxn][maxn];
int h[maxn][maxn];
void init(){clr(h,0);}
void update(int high,int x,int y,int mi){
for(int i = x;i <= maxn;i += lowbit(i)){
for(int j = y;j <= maxn;j += lowbit(j)){
if(h[i][j] != high)h[i][j] = high,c[i][j] = inf;
c[i][j] = min(c[i][j],mi);
}
}
}
int query(int high,int x,int y){
int res = inf;
for(int i = x;i >= 1;i-=lowbit(i)){
for(int j = y;j >= 1;j-=lowbit(j)){
if(h[i][j] == high)res = min(res,c[i][j]);
}
}
return res;
}
}bit[4];
void up(int d,int x,int y){
bit[0].update(d,x,y,dp[x][y]-x-y);
bit[1].update(d,x,m-y+1,dp[x][y]-x+y);
bit[2].update(d,n-x+1,m-y+1,dp[x][y]+x+y);
bit[3].update(d,n-x+1,y,dp[x][y]+x-y);
}
void qu(int d,int x,int y){
int &res = dp[x][y];res = inf;
res = min(res,bit[0].query(d-1,x,y)+x+y);
res = min(res,bit[1].query(d-1,x,m-y+1)+x-y);
res = min(res,bit[2].query(d-1,n-x+1,m-y+1)-x-y);//***
res = min(res,bit[3].query(d-1,n-x+1,y)-x+y);
}
int main(){
scanf("%d%d%d",&n,&m,&p);
for(int i = 1;i <= n;++i){
for(int j = 1;j <= m;++j){
int x;
scanf("%d",&x);
gap[x].push_back((node){i,j});
}
}
for(int i = 0;i < 4;++i)bit[i].init();
for(int i = 0;i < (int)gap[1].size();++i){
node p = gap[1][i];
int x = p.x,y = p.y;
dp[x][y] = x-1+y-1;
// printf("%d %d %d
",x,y,dp[x][y]);
up(1,x,y);
}
for(int d = 2;d <= p;++d){
for(int i = 0;i < (int)gap[d].size();++i){
node p = gap[d][i];int x = p.x,y = p.y;
qu(d,x,y);
}
for(int i = 0;i < (int)gap[d].size();++i){
node p = gap[d][i];int x = p.x,y = p.y;
up(d,x,y);
}
}
int x = gap[p][0].x,y = gap[p][0].y;
printf("%d
",dp[x][y]);
// for(int i = 1;i <= n;++i)for(int j = 1;j <= m;++j)
// printf("%d %d %d
",i,j,dp[i][j]);
return 0;
}
然而ggbbgg的暴力我也是zhui了直接爆搜,复杂度分析也不会，反正就是很玄学啦
#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int Maxn = 305;
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,-1,1 };
template <class T>
inline T Read(T& a) {
a = 0; char c = getchar();
while (c <'0' || c >'9') c = getchar();
while (c >= '0'&&c <= '9') {
a = (a << 3) + (a << 1) + c - '0';
c = getchar();
}
return a;
}
template <class T>
void clear(T& A) {
while (!A.empty()) A.pop();
}
#define inside(a,b) ((a)>0&&(a)<=(b))
inline int dist(int x1, int y1, int x2, int y2) { return abs(x1 - x2) + abs(y1 - y2); }
struct node{
int x, y, dis;
node(){}
node(int a, int b, int c) {
x = a; y = b; dis = c;
}
bool operator < (const node& A)const {
if (dis == A.dis) return x < A.x;
return dis < A.dis;
}
};
typedef pair<int, int>pii;
vector<pii>point[Maxn * Maxn];
int dp[Maxn][Maxn], n, m;
const int INF = 1 << 30;
int d[Maxn][Maxn];
void bfs(const int& nowkey,const int& curs,const int& lasts) {
memset(d, -1, sizeof(d));
vector<node>lst;
queue<node>q;
lst.clear(); clear(q);
for (int i = 0; i < lasts; ++i) {
int _x = point[nowkey - 1][i].first, _y = point[nowkey - 1][i].second;
lst.push_back(node(_x, _y, dp[_x][_y]));
}
sort(lst.begin(), lst.end());
int head = 0;
q.push(lst[head++]);
while (!q.empty()) {
int nx = q.front().x, ny = q.front().y, nd = q.front().dis;
q.pop();
while (head < lasts&&lst[head].dis <= nd)q.push(lst[head++]);
for (int i = 0; i < 4; ++i) {
int _x = nx + dx[i], _y = ny + dy[i];
if (inside(_x, n) && inside(_y, m) && !(~d[_x][_y])) {
d[_x][_y] = nd + 1;
q.push(node(_x, _y, d[_x][_y]));
}
}
}
for (int i = 0; i < curs; ++i) {
int _x = point[nowkey][i].first, _y = point[nowkey][i].second;
dp[_x][_y] = d[_x][_y];
}
}
int main() {
int p, a;
Read(n); Read(m); Read(p);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
Read(a);
point[a].push_back(make_pair(i, j));
if (a == 1) {
dp[i][j] = i + j - 2;
}else{
dp[i][j] = INF;
}
}
for (int i = 2; i <= p; ++i) {
int curs = point[i].size();
int lasts = point[i - 1].size();
if (curs*lasts <= n * m) {//控制这一层复杂度比m*n小
for (int j = 0; j < curs; ++j) {
int nowx = point[i][j].first, nowy = point[i][j].second;
for (int k = 0; k < lasts; ++k) {
int lastx = point[i - 1][k].first, lasty = point[i - 1][k].second;
dp[nowx][nowy] = min(dp[nowx][nowy], dp[lastx][lasty] + dist(nowx, nowy, lastx, lasty));
}
}
}
else bfs(i,curs,lasts);//如果裸的dp比m*n还大那么不如原始的爆搜
}
printf("%d", dp[point[p][0].first][point[p][0].second]);
return 0;
}