做网站一定要虚拟主机吗,免费网站排名优化软件,建行国际互联网网站,衣服定制的app有哪些题目#xff1b; 用动态规划很容易将完成任务量作为dp的阶段#xff0c;通过指派服务员#xff0c;从当前i-1个任务转移到i个任务#xff1b; 我们可以用一个四维数组f[i][x][y][z]来表示在完成当前任务i时#xff0c;三个机器人分别在x#xff0c;y#xff0c;z的位置 用动态规划很容易将完成任务量作为dp的阶段通过指派服务员从当前i-1个任务转移到i个任务 我们可以用一个四维数组f[i][x][y][z]来表示在完成当前任务i时三个机器人分别在xyz的位置每次由其中一个机器人向目标位置转移取min值 但是算法规模一点都不乐观 我们想到在完成当前任务i时必定存在一个机器人位于p[i],即目标地那么我们可以用f[i][x][y],即完成任务i时另外两个机器人位于xy的位置 状态转移 f[k][i][j]min(f[k][i][j],f[k-1][i][j]c[p[k-1]][p[k]]);//k为当前完成任务c数组记录两者间的距离p数组为目标到达地 f[k][p[k-1]][j]min(f[k][p[k-1]][j],f[k-1][i][j]c[i][p[k]]); f[k][i][p[k-1]]min(f[k][i][p[k-1]],f[k-1][i][j]c[j][p[k]]); 不妨设p03那么初始值f[0][1][2]0;目标为f[N][?][?]; 题后反思 求解线性dp要注意阶段的选择注意附加信息要处理 确定状态时要注意选择最小的能表示整个状态的维度空间 阶段保证无后效性 #includebits/stdc.h
#define maxl 201
#define maxn 1001
using namespace std;
int f[1001][201][201],n,m,t,l,c[201][201],p[1001],ans;
templatetypename Tinline void read(T x)
{x0;T f1,chgetchar();while(!isdigit(ch)) chgetchar();if(ch-) f-1, chgetchar();while(isdigit(ch)) x(x1)(x3)(ch^48), chgetchar();x*f;
}
int main()
{read(t);while(t--) {int ans2139062143;read(l);read(n);for(int i1;il;i)for(int j1;jl;j)read(c[i][j]);memset(f,0x7f,sizeof(f));for(int i1;in;i) {read(p[i]);}f[0][1][2]c[3][p[1]];f[0][2][3]c[1][p[1]];f[0][1][3]c[2][p[1]];p[0]3,f[0][1][2]0;for(int k1;kn;k)for(int i1;il;i)for(int j1;jl;j)if(i!jp[k-1]!jp[k-1]!i){f[k][i][j]min(f[k][i][j],f[k-1][i][j]c[p[k-1]][p[k]]);f[k][p[k-1]][j]min(f[k][p[k-1]][j],f[k-1][i][j]c[i][p[k]]);f[k][i][p[k-1]]min(f[k][i][p[k-1]],f[k-1][i][j]c[j][p[k]]);}for(int i1;il;i)for(int j1;jl;j) {if(i!ji!p[n]j!p[n])ansmin(ans,f[n][i][j]);}printf(%d\n,ans);}return 0;
} View Code 转载于:https://www.cnblogs.com/Tyouchie/p/10668379.html
