本题本质上是一个 带资源约束的有向无环图（DAG）最长路径问题，可以通过 动态规划 求解。
1. 问题建模
我们将表世界和里世界的每一个位置视为状态节点。
状态空间：共有 个节点。 表示表世界第 个点， 表示里世界第 个点。
初始状态： 为起点，初始收益为 。 不可作为起点。
边的定义（从
展开全文
由于不知道最后是从哪个出口出来的，所以状态数组为二维，维护两个世界dp[3][200010]每个位置由当前世界推移过来和从另一世界转移过来，所以状态转移方程：dp[1][i]=max(dp[1][i-1],dp[2][i-1]-k)+dp[1][i]只在dp[2][i-1]>=k的情况下满足，
展开全文
显然这题可以用动态规划求解，而且发现只与上一个状态有关，所以可以滚动，详情看代码
int n, k;
rd(n, k);
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) rd(a[i]);
ll
展开全文
动态规划定义 dp[i][0] 和 dp[i][1] 两个状态：dp[i][0]：Askalana 到达表世界第 i 号点时，能拥有的最大金币数。dp[i][1]：Askalana 到达里世界第 i 号点时，能拥有的最大金币数。初始化只有初始状态可达：dp[1][0] = a[1]（初始在表世界 1
展开全文
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
ios_base
展开全文
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n, k;
cin >> n >> k;
vector&l
展开全文
思路：非常裸的状态机dp板子题，挺典型的，建议没有接触过状态机dp的朋友们好好学习
代码：
import sys
input = lambda: sys.stdin.readline().strip()
import math
inf = 10 ** 18
def I():
return
展开全文
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,k;
int a[N],b[N];
int dp[N][2];
signed main()
{
展开全文
dp一下 dp[i][j]表示到i行j列能得到的最多金币数量，那么i行j列可以从i行j-1列跟i^1行j-1列转移，注意一下转移条件就可以了，最后答案给dp[0][n],dp[1][n]取一下max就行了
void solve(){
int n,k;
cin>>n>
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
