1575. Count All Possible Routes
题目大意
给定一些不同的位置 $(N \le 100)$，给定起点和终点位置的标号，给定起始油量 $(F \le 200)$。
每次可以选择从当前位置走到任意其他位置花费每单位距离 $1$ 单位油。油量不能为负。
问，从起点到终点总共有多少种走法。
简要题解
法1：
本题中 $N$ 和 $F$ 的值都不是很大，考虑动态规划很容易设计出动态规划状态
$ dp[当前油量为 i ][当前所在点位为 j] $ 的方案数
注意到，油量总是从较小的推导较大的，由于位置彼此不同，不会存在相同油量的状态互相推导，于是这样的状态设计是可转移的。
很容易写出复杂度为 $O(N^2 F)$ 的动态规划。
代码实现
class Solution {
public:
typedef pair<int,int> PII;
int MO=1e9+7;
void addv(int &x,int y)
{
if(x==-1) x=0;
x+=y;
if(x>=MO) x-=MO;
}
int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
int n=locations.size();
vector<vector<int> > dp(n,vector<int>(fuel+1,-1));
dp[start][fuel]=1;
for(int j=fuel;j>0;j--)
{
for(int u=0;u<n;u++)
{
if(dp[u][j]==-1) continue;
// cout<<u<<" "<<j<<endl;
for(int v=0;v<n;v++)
{
if(u==v) continue;
int d=abs(locations[u]-locations[v]);
if(d>j) continue;
addv(dp[v][j-d],dp[u][j]);
}
}
}
int ans=0;
for(int i=0;i<=fuel;i++)
if(dp[finish][i]!=-1) addv(ans,dp[finish][i]);
return ans;
}
};
法2：
注意到当三个位置的关系为 $a$,$b$,$c$ 这样排列时，如果从 $a$ 走到 $c$ 总会通过 $b$。
换句话说，所有从左侧点走到 $c$ 的都必须经过 $b$，因此考虑转移时只考虑从相邻位置转移过来。
$ dp[当前油量为 i ][当前所在点位为 j][状态为 k] $ 的方案数
$k = 0$，代表是停在 $j$ 点中转
$k = 1$，代表没有停，从左到右通过了 $j$
$k = 2$，代表没有停，从右到左通过了 $j$
复杂度
$T$： $O(NF)$
$S$： $O(NF)$
代码实现
const int M=105;
const int MF=205;
const int MO=1e9+7;
void addv(int &x,int y)
{
x+=y;
if(x>=MO) x-=MO;
}
int dp[MF][M][3];
class Solution {
public:
int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
memset(dp,0,sizeof(dp));
int n=locations.size();
int vs=locations[start],ve=locations[finish];
sort(locations.begin(),locations.end());
for(int i=0;i<n;i++)
{
if(locations[i]==vs) start=i;
if(locations[i]==ve) finish=i;
}
dp[fuel][start][0]=1;
for(int i=fuel;i>0;i--)
{
for(int j=0;j<n;j++)
{
if(j)
{
int d=locations[j]-locations[j-1];
if(d<=i)
{
addv(dp[i-d][j-1][0],dp[i][j][0]);
addv(dp[i-d][j-1][0],dp[i][j][1]);
addv(dp[i-d][j-1][1],dp[i][j][0]);
addv(dp[i-d][j-1][1],dp[i][j][1]);
}
}
if(j!=n-1)
{
int d=locations[j+1]-locations[j];
if(d<=i)
{
addv(dp[i-d][j+1][0],dp[i][j][0]);
addv(dp[i-d][j+1][0],dp[i][j][2]);
addv(dp[i-d][j+1][2],dp[i][j][0]);
addv(dp[i-d][j+1][2],dp[i][j][2]);
}
}
}
}
int ans=0;
for(int i=0;i<=fuel;i++)
addv(ans,dp[i][finish][0]);
return ans;
}
};
Next: [AtCoder] Beginner Contest 176 E - Bomber