tyvj1061 Mobile Service


线性dp,注意初始化以及三个点不能相同,还有不要弱智爆内存

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int l,n,c[500][500],f[1005][205][205],p[1050];
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
int main()
{
    l=read(),n=read();
    for(int i=0;i<=n;i++)
        for(int j=1;j<=l;j++)
            for(int k=1;k<=l;k++) f[i][j][k]=inf;
    for(int i=1;i<=l;i++)
        for(int j=1;j<=l;j++)
        c[i][j]=read();
    for(int i=1;i<=n;i++) p[i]=read();
    f[0][1][2]=0;p[0]=3;
    for(int i=0;i<=n-1;i++)
        for(int j=1;j<=l;j++)
            for(int k=1;k<=l;k++)
            {
                if(p[i+1]!=j&&j!=k&&k!=p[i+1]) f[i+1][j][k]=min(f[i+1][j][k],f[i][j][k]+c[p[i]][p[i+1]]);
                if(p[i+1]!=p[i]&&p[i]!=k&&k!=p[i+1]) f[i+1][p[i]][k]=min(f[i+1][p[i]][k],f[i][j][k]+c[j][p[i+1]]);
                if(p[i+1]!=j&&j!=p[i]&&p[i]!=p[i+1]) f[i+1][j][p[i]]=min(f[i+1][j][p[i]],f[i][j][k]+c[k][p[i+1]]);
            }
    int ans=inf;
    for(int i=1;i<=l;i++)
        for(int j=1;j<=l;j++)if(i!=j) ans=min(ans,f[n][i][j]);
    printf("%d\n",ans);
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
P1880 NOI1995石子合并 P1880 NOI1995石子合并
继续重新学dp,当年写的代码真是丑,一点缩进都没有… 基本区间dp,由于是环形,先复制一份然后继续求解,可以发现区间长度可以递增,把它作为状态,之后枚举左端点,求出右端点,然后在这中间枚举端点,进行更新。之后在扫一遍去最优就好了 #inc
2019-07-06
下一篇 
P2678跳石头 P2678跳石头
二分经典题,不过n=0的边界情况要特判一下 #include<bits/stdc++.h> using namespace std; const int maxn=100050; inline int read() { in
2019-07-06
  目录