2021蓝桥杯省赛B组题目（C/C++）E.路径
最短路径, 因为变化情况比较多, 所以开始想的是深搜, 但是太慢了, 跑不出来, 后来就想着优化一下, 有的地方到另一个地方可能会考虑很多遍, 于是考虑了DP
#include <bits/stdc++.h> using namespace std; typedef long long LL;
typedef pair<int,int> PII;
const int N = 1e8+10, M = 21;
LL res = 9999999999999;
LL f[2880][30], ff[200030];//数组开的比较大, 怕爆
//ff[i]是到i的最短路, f[i][j]从i开始走j步后一共需要走多少
//这题还不算难, 随便开个二维的就能过了 , 但是当时没想出来 int main()
{
int n = 2021;
for(int i = 0; i <= 20000; i ++) ff[i] = 9999999999999;
ff[1] = 0; for(int i = 1; i < n; i ++)
for(int j = 1; j <= 21; j ++)
{ LL xx = ff[i]+(LL)i*(i+j)/__gcd(i, i+j);
f[i][j] = xx, ff[i+j] = min(ff[i+j],xx);
if(ff[i+j]==0)cout << i << ' '<<j <<'\n';
}
cout <<ff[2021]<< '\n';
return 0;
}
