当前位置：首页 > news >正文

【Luogu】动态规划二

news 2025/6/9 6:44:31

P6205 [USACO06JAN] Dollar Dayz S - 洛谷

思路：

没啥好说的，转移方程显然是 dp[i] += dp[i- j]，初始化 dp[0] = 1，双重循环时注意第二层从 i 开始，特殊的这一题要使用 int128，否则会爆掉，所以还需要手写输出

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endl__int128 dp[10001];
void write(__int128 x)
{if (x > 9) write(x / 10);//如果x>9的话就递归它的最高位，再往下依次输出 putchar(x % 10 + '0');//输出这个数的末尾/kk（+'0'是为了让它转成字符类型的 
}
void solve()
{int n, k;cin >> n >> k;dp[0] = 1;for (int i = 1; i <= k; i++){for (int j = i; j <= n; j++){dp[j] += dp[j - i];}}write(dp[n]);
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

P1649 [USACO07OCT] Obstacle Course S - 洛谷

思路：

不知道为什么里面还有个bfs

由于这一题求的不是最短路，而是最少转向次数，那我们就要转换思路了

既然我们只需要知道最少转向数，那我们最优的解法肯定是沿着一条线走，所以我们可以对于每个点枚举四个方向，一直到无法走（到了边界或者x上），那么每次的转向次数 + 1 即可，为了防止同一个点反复走，我们可以定义一个res数组，用于储存 x,y 处最少的转向数（有点迪杰斯特拉的感觉），然后就是常规的暴力枚举了

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlchar mp[105][105];
pair<int, int> s, e;
pair<int, int> dir[4] = { {1,0},{-1,0},{0,1},{0,-1} };
int n;
vector<vector<int>> res(105,vector<int>(105,1e9));
void bfs()
{queue<pair<int, int>> q;q.push(s);res[s.first][s.second] = -1;while (!q.empty()){auto t = q.front();q.pop();if (t == e){return;}for (int i = 0; i < 4; i++){int nextx = dir[i].second + t.second;int nexty = dir[i].first + t.first;while (1){if (nextx < 1 || nexty < 1 || nextx > n || nexty > n || mp[nexty][nextx] == 'x'){break;}if (res[nexty][nextx] > res[t.first][t.second] + 1){res[nexty][nextx] = res[t.first][t.second] + 1;q.push({ nexty,nextx });}nextx += dir[i].second;nexty += dir[i].first;}}}
}void solve()
{cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){cin >> mp[i][j];if (mp[i][j] == 'A'){s = { i,j };}if (mp[i][j] == 'B'){e = { i,j };}}}bfs();if (res[e.first][e.second] >= 1e9){cout << -1;return;}cout << res[e.first][e.second];
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

P6208 [USACO06OCT] Cow Pie Treasures G - 洛谷

思路：

金字塔倒过来版本

操作还是一样的，但是我们要注意一个特点，左下角会有一个三角形区域是无法走过的，所以枚举时要特别注意要保证第二层不能超过第一层

转移方程题目直接告诉你了，直接抄即可

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlvoid solve()
{int r, c;cin >> r >> c;vector<vector<int>> a(r + 2, vector<int>(c + 2,0));vector<vector<int>> dp(r + 2, vector<int>(c + 2, 0));for (int i = 1; i <= r; i++){for (int j = 1; j <= c; j++){cin >> a[i][j];}}for (int j = 1; j <= c; j++){for (int i = 1; i <= r && i <= j; i++){dp[i][j] = max(dp[i][j-1], max(dp[i + 1][j - 1], dp[i - 1][j - 1])) + a[i][j];}}cout << dp[r][c];
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

查看全文

http://www.xdnf.cn/news/108631.html