Time Limit: 3 second
Memory Limit: 256 MB
【问题描述】
一个公司有三个移动服务员。如果某个地方有一个请求，某个员工必须赶到那个地方去（那个地方没有其他员工），某一时刻只有一个员工能移动。被请求后，他才能移动，不允许在同样的位置出现两个员工。从P到Q移动一个员工，需要花费C(P，Q)。这个函数没有必要对称，但是C(P，P)＝0。公司必须满足所有的请求。目标是最小化公司花费。
【输入格式】
第一行有两个整数L，N（3≤L≤200，1≤N≤1000）。L是位置数，N是请求数。每个位置从1到L编号。下L行每行包含L个非负整数。第i+1行的第j个数表示c(I，J )，并且它小于2000。最后一行包含N个数，是请求列表。一开始三个服务员分别在位置1，2，3.
【输出格式】
一个数M，表示最小服务花费
【输入样例1】
5 9
0 1 1 1 1
1 0 2 3 2
1 1 0 4 1
2 1 5 0 1
4 2 3 4 0
4 2 4 1 5 4 3 2 1
【输出样例1】
5
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t029
【题意】
【题解】
由于是按顺序处理请求的.
所以每当完成一个请求i过后.
三个人中必然有一个人是在Ask[i]所在的位置的;
这样就能给DP降维了；
假设f[i][j][k]表示前i个询问,第i个询问过后,有一个人是在Ask[i]处,另外两个人是在j,k处(这里时刻保证j< k)的最小花费;
则有三种转移到i+1的方式
1.从j->Q[i+1];
2.从k->Q[i+1];
3.从Q[i]->Q[i+1];
看看到了i+1后新的状态另外两个人在哪里就好;
代码挺简单的。
平台给的内存限制比较大。所以直接开F[N][L][L]没问题;
如果内存小的话就要用滚动数组了.
【完整代码】
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
#define ref(x) scanf("%lf",&x)
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int L = 210, N = 1e3 + 20;
const int INF = 0x3f3f3f3f;
int w[L][L],l,n,Q[N];
int ans = 20e8;
int f[N][L][L];
void in()
{
rei(l), rei(n);
rep1(i, 1, l)
rep1(j, 1, l)
rei(w[i][j]);
rep1(i, 1, n)
rei(Q[i]);
}
void ga()
{
if (Q[1]!=1 && Q[1]!=2)
f[1][1][2] = w[3][Q[1]];
if (Q[1] != 1 && Q[1] != 3)
f[1][1][3] = w[2][Q[1]];
if (Q[1] != 2 && Q[1] != 3)
f[1][2][3] = w[1][Q[1]];
rep1(i,1,n-1)
rep1(j,1,l-1)
rep1(k, j + 1, l)
if (f[i][j][k]<INF)
{
//j->Q[i+1]
if (k != Q[i + 1] && Q[i] != Q[i + 1])
{
int one = k, two = Q[i];
if (one > two) swap(one, two);
f[i + 1][one][two] = min(f[i + 1][one][two], f[i][j][k] + w[j][Q[i + 1]]);
}
//k->Q[i+1];
if (j != Q[i + 1] && Q[i] != Q[i + 1])
{
int one = j, two = Q[i];
if (one > two) swap(one, two);
f[i + 1][one][two] = min(f[i + 1][one][two], f[i][j][k] + w[k][Q[i + 1]]);
}
//Q[i]->Q[i+1]
if (j != Q[i + 1] && k != Q[i + 1])
{
f[i + 1][j][k] = min(f[i + 1][j][k], f[i][j][k] + w[Q[i]][Q[i + 1]]);
}
}
rep1(i, 1, l - 1)
rep1(j, i + 1, l)
ans = min(ans, f[n][i][j]);
}
void o()
{
printf("%d
", ans);
}
int main()
{
//printf("%d
", sizeof(f) / 1024 / 1024);
//freopen("F:\rush.txt", "r", stdin);
memset(f, INF, sizeof f);
in();
ga();
o();
//printf("
%.2lf sec
", (double)clock() / CLOCKS_PER_SEC);
return 0;
}