Min酱要旅行 牛客DP入门

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

0x00 题目来源

Min酱要旅行

0x10 Tag

01背包，滚动数组

0x20 题目描述

---

0x30 思路与算法

我们在这里简单分析一下复杂度，假设我们记录不选取某个物品$k$，当前选取的物品$i$，背包剩余的容量$j$。则至少开一个char f[MAXN][MAXN][MAXN]的数组。在这里$MAXN=2305$,空间复杂度就会爆炸($8\cdot 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;
}

---

0x40 另

=)

这篇关于Min酱要旅行 牛客DP入门的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---