【算法题】动态规划-旅行

题目描述

【算法题】动态规划-旅行
示例1
输入:

4 2 7
1 2 3 4

输出:

18

说明:

2到7的合法路径有:
2->1->5->6->7,长度为4
2->3->4->8->7,长度为7
2->3->7,长度为4
2->6->7,长度为3
长度和为4+7+4+3=18

链接:https://ac.nowcoder.com/acm/contest/12949/F
来源:牛客网

思路解析:这是今天下午参加牛客比赛的最后一题,比较有意思。看起来是个图论相关的,仔细分析所以动态规划,里面的转态转移要搞懂。题目的意思是找出从点S到点t的所有不重复且没有重复点的道路,然后累加计算路径和。所以我们将所以的路径都找出来,如果简单的使用广搜加判重,代码结构与时间复杂度会很高,有许多不符合要求的转态会被搜索到,所以使用动态规划才是这道题的正解。
使用动态规划第一要分析转态的转移。它可能是下面的这种状态。
这时可以将它分成三部分:
第一部分:计算点s到点s+n的路径和与路径种类。这里只存在一些[型的路径。即
4-n4
4-3-n3-n4
4-3-2-n2-n3-n4
4-3-2-1-n1-n2-n3-n4
共4种,即种类数 f[s][1]=s;
路径和:g[s][1]=(a1+…+a4)+(1+1+2+2+3+3+4+4)=(a1+…+a4)+4*3;
第二部分:计算(s,t)存在二个方向的状态转移;
由图可发现,走到点n4有二个方向进行状态转移,同样走到点5有二个方向进行状态转移;即可由初始状态点4与点n4二个状态不同转移得到点t与点n(t-1)的状态。此时还还剩余点n(t+1)的状态未得到。
第三部分:[t,n]只存在一个方向的转态转移。
计算点n(t+1),该状态用点出发t不断进行状态转移得到。此时要注意状态的组合产生新的状态,而不是单纯的转移。
最后:最终答案的nt状态可用点t、点n(t-1)与点n(t+1)得到
【算法题】动态规划-旅行
具体代码:

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

#define mp make_pair
const int N=1e5+10;
typedef long long ll;
const ll M=998244353;  //余数
int n,s,t;
ll a[N];
ll g[N][2];//到达该点所有道路的和
ll f[N][2];//到达该点道路种类数

void solve()
{
    scanf("%d %d %d",&n,&s,&t);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    t-=n;  //转换为表第二行的序号
    //思路:将网格图分成三部分:
    //第一部分:[0,s]只存在一些[型的路;
    //第二部分:(s,t)存在二个方向的状态转移;
    //第三部分:[t,n]只存在一个方向的转态转移。
    ll sum=0;
    for(int i=1;i<=s;i++) sum+=a[i];
    f[s][1]=s;
    g[s][1]=(sum+(s-1ll)*s)%M;     //第一部分:[0,s]只存在一些[型的路;
    f[s][0]=1;
    g[s][0]=0;
    for(int i=s+1;i<t;i++) {    //第二部分:(s,t)存在二个方向的状态转移;
        f[i][0]=(f[i-1][0]+f[i-1][1])%M;
        g[i][0]=(g[i-1][0]+f[i-1][0]+g[i-1][1]+(1+a[i])*f[i-1][1]%M)%M;
        f[i][1]=(f[i-1][0]+f[i-1][1])%M;
        g[i][1]=(g[i-1][1]+f[i-1][1]+g[i-1][0]+(1+a[i])*f[i-1][0]%M)%M;
    }
    ll ans=f[t-1][1]+g[t-1][1];
    ans%=M;
    sum=0;
    //第三部分:[t,n]只存在一个方向的转态转移。
    for(int i=t;i<=n;i++) sum+=a[i];
    ans+=(f[t-1][0]*(n-t+1+sum%M+(n-t)*(n-t+1ll)%M)%M+g[t-1][0]*(n-t+1)%M)%M;   
    printf("%lld\n",ans%=M);
}

int main()
{
    solve();
    return 0;
}
上一篇:蓝桥杯—稍小分数—java


下一篇:算法分析:三个数的最大乘积