Min酱要旅行牛客DP入门

本文主要是介绍Min酱要旅行牛客DP入门，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

0x00 题目来源

Min酱要旅行

0x10 Tag

01背包，滚动数组

0x20 题目描述

在这里插入图片描述

0x30 思路与算法

我们在这里简单分析一下复杂度，假设我们记录不选取某个物品 $k$ ，当前选取的物品 $i$ ，背包剩余的容量 $j$ 。则至少开一个char f[MAXN][MAXN][MAXN]的数组。在这里 $M A X N = 2305$ ,空间复杂度就会爆炸( $8·10^9$ )。时间复杂度易证超出限制。

所以我们考虑反向解决问题。我们可以先求解没有限制时的动态转移方程。对于物品 $i$ ，选择的方案数量为整体选择方案不选 $i$ 的方案数与整体选择方案选 $i$ 的方案数之和，动态转移方程记作： $f (x) = f (x) + f (x - a [i])$

在这里我们选择滚动数组解答该题目， $f (x)$ 代表当前容积为 $x$ 的方案数之和， $a [i]$ 为物品 $i$ 的体积， $x$ 为当前容积。
这是一个比较标准的01背包滚动数组转移
$f (x - a [i])$ 代表已经选择了物品 $i$ ， $f (x)$ 则是没有选择物品 $i$ 就已经到达容积 $x$ 。

那么对于题设而言，限制不能选择物品 $i$ 的方案数为：无限制选择的方案数-有限制下选择了物品 $i$ 的方案数。我们假设 $g (x)$ 代表有限制下当前容积为 $x$ 的方案数之和，动态转移方程记作： $g (x) = f (x) - g (x - a [i])$

$g (x - a [i])$ 代表已经选择了物品 $i$
$f (x)$ 与 $g (x)$ 本质是一样的，只是有没有限制
总体时间复杂度为 $O(n^2)$

但如果当前容积为 $x$ 小于 $a [i]$ ，则 $g (x) = f (x)$ 。（因为就算没有限制也选不了物品 $i$ 了）

0x31 代码实现

实现细节

else g[j]=((f[j]-g[j-a[i]])+10)%10;

由于进行减法操作，结果有可能为负数，必须加上模数保证取模正确。

    for(int i=1;i<=n;++i){for(int j=m;j>=a[i];--j){f[j]=(f[j]+f[j-a[i]])%10;}}

对于最基础的滚动数组，逆序转移，在空间不够的时候停止转移。

0x32 完整代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const ll INF = 0x3f3f3f3f;
// <------------------------------->
#define endl "\n"
#define space " "
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define HACK freopen("test.in", "r", stdin);freopen("test.out", "w", stdout);
#define RT double rtime = 1.0 * clock() / CLOCKS_PER_SEC;cout<<"\nRuntime: "<<rtime<< " s.\n";
#define debug(x) cout<<"target is "<<x<<endl
#define debug_arr(arr) for(auto x:arr) cout<<x<<" "; cout<<"\n";
// <------------------------------->
const int MAXN=2305;
int f[MAXN];
int g[MAXN];
// <------------------------------->
int main()
{IOS;#ifdef LOCAL_JUDGEHACK;#endifint n,m;cin>>n>>m;vector<int>a(n+1);for(int i=1;i<=n;++i)cin>>a[i];f[0]=1;for(int i=1;i<=n;++i){for(int j=m;j>=a[i];--j){f[j]=(f[j]+f[j-a[i]])%10;}}for(int i=1;i<=n;++i){for(int j=0;j<=m;++j){if(j<a[i]) g[j]=f[j];else g[j]=((f[j]-g[j-a[i]])+10)%10;}  for(int j=1;j<=m;++j)cout<<g[j];cout<<endl;}#ifdef LOCAL_JUDGERT;#endifreturn 0;
}