Main » 2013 August 23 » [noip] 移动服务
10:15 AM [noip] 移动服务 |
较难DP，一开始只想到了N^3*L的算法Prob.1597: [NOIP2010模拟赛]移动服务Time Limit: 6 Sec Memory Limit: 640 MBSubmit: 62 Solved: 32 [Submit][Status][Web Board] Description一个公司有三个移动服务员。如果某个地方有一个请求，某个员工必须赶到那个地方去（那个地方没有其他员工） ，某一时刻只有一个员工能移动。被请求后，他才能移动，不允许在同样的位置出现两个员工。从 p 到 q 移动一个员工，需要花费 c(p,q)。这个函数没有必要对称，但是 c(p,p)=0。公司必须满足所有的请求。目标是最小化公司花费。 Input第一行有两个整数 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。 Output一个数 M，表示最小服务花费。 Sample Input5 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 Sample Output5 HINTSourceCode. #include<cstdio> #include<cstdlib> #include<cstring> #define M 210 #define N 1010 int dp[N][M][M],n,l,pos[N],c[N][N]; int min(int a,int b) { if (a<b) return a; return b; } int DP() { int i,j,k; for (i=1;i<=n;i++) { int old_p=pos[i-1],new_p=pos[i]; for (j=1;j<=l;j++) for (k=1;k<=l;k++) if ((j!=k)&&(k!=old_p)&&(j!=old_p)) if (dp[i-1][j][k]<1600085855) { dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]+c[old_p][new_p]); dp[i][old_p][k]=min(dp[i][old_p][k],dp[i-1][j][k]+c[j][new_p]); dp[i][j][old_p]=min(dp[i][j][old_p],dp[i-1][j][k]+c[k][new_p]); } } int old_p=pos[n-1]; int res=1000000000; for (j=1;j<=l;j++) for (k=1;k<=l;k++) //if ((j!=k)&&(k!=old_p)&&(j!=old_p)) if (dp[n][j][k]<res) res=dp[n][j][k]; return res; } int main() { scanf("%d %d",&l,&n); int i,j; for (i=1;i<=l;i++) for (j=1;j<=l;j++) scanf("%d",&c[i][j]); for (i=1;i<=n;i++) scanf("%d",&pos[i]); memset(dp,0x5f,sizeof(dp)); pos[0]=1;dp[0][2][3]=0; int ans=2000000000; ans=min(DP(),ans); memset(dp,0x5f,sizeof(dp)); pos[0]=2;dp[0][1][3]=0; ans=min(DP(),ans); memset(dp,0x5f,sizeof(dp)); pos[0]=3;dp[0][1][2]=0; ans=min(DP(),ans); printf("%d\n",ans); } |
|
|
| Total comments: 0 | |