问题

给定一个平面，以及一些点之间的边，求出一条最长的环形路径

解决方案

一般可以使用DP解决，但是为了避免重复路径，需要控制状态转移方程的条件和边界

一般问题

给定n个点，以及两点之间的边，求出起点到终点的两条不重复路径最多经过多少点
DP方程： Fi=max{Fi+1,Fk+1}
注意：此时DP顺着推会更加清晰，边界控制也相对简单

#include <bits/stdc++.h>
using namespace std;

string a[105],x,y;
int head[105],f[105][105],Next[20005],en[20005],cnt,n,v;

void add(int x,int y){
    cnt++;
    Next[cnt]=head[x];
    head[x]=cnt;
    en[cnt]=y;
}

int main(){
    cin>>n>>v;
    for (int i=1;i<=n;++i) cin>>a[i];
    memset(f,0xcf,sizeof f);
    for (int i=1;i<=v;++i){
        cin>>x>>y;
        int l,r;
        for (int i=1;i<=n;++i) if (a[i]==x) l=i;
        for (int i=1;i<=n;++i) if (a[i]==y) r=i;
        add(l,r);
        add(r,l);
    }
    f[1][1]=0;
    for (int i=1;i<=n;++i){
        for (int j=1;j<=n;++j){
            if (j==i && i!=1) continue;  //因为不能重复，但是i=j=1时也能转移
            for (int k=head[i];k;k=Next[k]){
                if (en[k]>i && en[k]>j ||en[k]==n) f[en[k]][j]=max(f[en[k]][j],f[i][j]+1);
            } //找到接在i后的一个点，注意K点必须在ij的后面，不然情况会重复，不要忘记ij其中一个到达N时，也要继续转移，不然最终答案为-INF
            for (int k=head[j];k;k=Next[k]){
                if (en[k]>i && en[k]>j ||en[k]==n) f[i][en[k]]=max(f[i][en[k]],f[i][j]+1);
            }
        }
    }
    cout<<f[n][n]<<endl;
    return 0;
}

有条件的转移问题

HERE
设DPi为上面路径达到I，下面的路径达到J时的最短路径长度之和，其它与上面相同，但当I，J为特殊点时，只有一种转移方案

#include <bits/stdc++.h>
using namespace std;

struct node{
    int x,y;
}a[1005];
int n,tb,eb;
double f[1005][1005],ans;

double get(int st,int ed){
    int t=a[st].x-a[ed].x;
    int tt=a[st].y-a[ed].y;
    return sqrt(t*t+tt*tt);
}

int main(){
    cin>>n>>tb>>eb;
    for (int i=1;i<=n;++i) scanf("%d %d",&a[i].x,&a[i].y);
    tb++;eb++;
    for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) f[i][j]=1e7;
    f[1][1]=0;
    for (int i=1;i<=n;++i){
        for (int j=1;j<=n;++j){
            if (i!=j || i==1){ //注意转移方程的条件 I!=J
                int k=max(i,j)+1;
                if (k==n+1) k=n;
                if (k!=tb){
                    f[i][k]=min(f[i][k],f[i][j]+get(j,k)); //判断能否转移过来
                }
                if (k!=eb){
                    f[k][j]=min(f[k][j],f[i][j]+get(i,k));
                }
            }
        }
    }
    printf("%.2lf",f[n][n]);
    return 0;
}

二维平面内的转移

例： 传纸条
DPik表示两条路径分别到达(i,j),(k,l)的最大值，转移基本相同

#include <bits/stdc++.h>
using namespace std;

int n,m,a[55][55],f[55][55][55][55];

int main(){
    cin>>m>>n;
    swap(m,n);
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            scanf("%d",&a[i][j]);
        }
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            for (int k=1;k<=n;++k){
                for (int l=j+1;l<=m;++l){
                    if (i!=j || k!=m){
                        f[i][j][k][l]=max( max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]) , max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]) ) +a[i][j]+a[k][l];
                    }
                }
            }
        }
    }
    cout<<f[n][m-1][n-1][m]<<endl;
    return 0;
}

由于循环变量中，只要知道了其中3个，便可求出第4个，因此可以降一维复杂度

#include <bits/stdc++.h>
using namespace std;

int n,m,a[55][55],f[105][55][55];

int main(){
    cin>>m>>n;
    swap(m,n);
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            scanf("%d",&a[i][j]);
        }
    }
    for (int k=1;k<=n+m-1;++k)
        for (int i=1;i<=n;++i){
            for (int j=1;j<=n;++j){
                if (k-i+1<1 || k-j+1<1) continue;
                if (i!=j) f[k][i][j]=max( max(f[k-1][i][j],f[k-1][i-1][j]) , max(f[k-1][i][j-1],f[k-1][i-1][j-1]))+a[i][k-i+1]+a[j][k-j+1];
            }
        }
    cout<<f[n+m-2][n-1][n]<<endl;
    return 0;
}

注意最后的输出状态

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/84/