JZTXT

Acwing提高课动态规划 DynamicProgram

发布时间 2023-03-22 21:13:25作者: 哲远甄骏

Acwing算法提高课背包模型(代码)

采药

// Problem: 采药
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/425/
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int n, m, v, w;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> m >> n;
	for(int i = 0; i < n ; i++)
	{
		cin >> v >> w;
		for(int j = m; j >= v; j--)
		{
			f[j] = max(f[j], f[j - v] + w);
		}
	}
	cout << f[m] << "\n";
	return 0;
}

装箱问题

// Problem: 装箱问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1026/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int n, m, v;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
		cin >> v;
		for(int j = n; j >= v; j--)
		{
			f[j] = max(f[j], f[j - v] + v);
		}
	}
	
	
	cout << n - f[n] << "\n";
	
	
	return 0;
}

宠物小精灵之收服

// Problem: 宠物小精灵之收服
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1024/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 +10, M = 500 + 10;

int n, V1, V2;
int f[N][M];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> V1 >> V2 >> n;
	
	for(int i = 0; i < n; i++)
	{
		int v1, v2;
		cin >> v1 >> v2;
		
		for(int j = V1; j >= v1; j--)
		{
			for(int k = V2 - 1; k >= v2; k--)
			{
				f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
			}
		}
	}	
	
	cout << f[V1][V2 - 1] << " ";
	int k = V2 - 1;
	
	while(k && f[V1][k - 1] == f[V1][V2 - 1]) k--;
	
	cout << V2 - k << "\n";
	return 0;
}

数字组合

// Problem: 数字组合
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/280/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int n, m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	f[0] = 1;
	for(int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		for(int j = m; j >= a; j--)
		{
			f[j] += f[j - a];
		}
	}
	
	cout << f[m] << "\n";
	return 0;
}

买书

// Problem: 买书
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1025/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n;

int f[N];
int v[] = {10, 20, 50, 100};


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	
	cin >> n;
	f[0] = 1;
	
	for(int i = 0; i < 4; i++)
	{
		for(int j = v[i]; j <= n; j++)
		{
			f[j] += f[j - v[i]];
		}
	}
	
	cout << f[n] << "\n";
	return 0;
}

货币系统

// Problem: 货币系统
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1023/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 3e3 + 10;
typedef long long ll;
int n, m;
ll f[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	f[0] = 1;
	for(int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		for(int j = a; j <= m; j++)
		{
			f[j] += f[j - a];
		}
	}
	
	cout << f[m] << "\n";
	
	
	return 0;
}

货币系统

// Problem: 货币系统
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/534/
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10;
int a[100], f[N];
int n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--)
    {
        memset(f, 0, sizeof f);
        cin >> n;
        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        sort(a, a + n);
        m = a[n - 1];
        f[0] = 1;

        int res = 0;
        for(int i = 0; i < n; i++)
        {
            if(!f[a[i]]) res++;
            for(int j = a[i]; j <= m; j++)
            {
                // f[j] += f[j - a[i]];
                f[j] |= f[j - a[i]];//思考为什么这样就可以
            }
        }
        cout << res << "\n";
    }

    return 0;
}

多重背包问题III

// Problem: 多重背包问题 III
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/6/
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;

int n, m;
int f[N], g[N], q[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	for(int i = 0; i < n; i++)
	{
		int v, w, s;
		cin >> v >> w >> s;
		memcpy(g, f, sizeof f);
		
		for(int j = 0; j < v; j++)
		{
			int hh = 0, tt = -1;
			
			for(int k = j; k <= m; k += v)
			{
				if(hh <= tt && q[hh] < k - s * v) hh++;
				//明白j - v的转移，j可以认为是m。m是由m - v 转移而来。
				while(hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt--;
				q[++tt] = k;
				f[k] = g[q[hh]] + (k - q[hh]) / v * w;
			}
		}
	}
	
	cout << f[m] << "\n";
	return 0;
}

庆功会

  • 普通版
// Problem: 庆功会
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/1021/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int f[N];
int n, m;
int v, w, s;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	
	cin >> n >> m;
	
	for(int i = 0; i < n; i++)
	{
		cin >> v >> w >> s;
		
		for(int j = m; j >= v; j--)
		{
			for(int k = 0; k <= s && k * v <= j; k++)
			{
				f[j] = max(f[j], f[j - k * v] + k * w);
			}
		}
	}
	cout << f[m] << "\n";
	
	return 0;
}
  • 二进制优化
// Problem: 庆功会
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/1021/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)


#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int n, m;
int a, b, s;
int f[N], v[N], w[N];
int cnt;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	
	cin >> n >> m;
	
	for(int i = 0; i < n; i++)
	{
		cin >> a >> b >> s;
		
		int k = 1;
		while(k <= s)
		{
			cnt++;
			v[cnt] = k * a;
			w[cnt] = k * b;
			s -= k;
			k *= 2;
		}
		if(s)
		{
			cnt++;
			v[cnt] = s * a;
			w[cnt] = s * b;
		}
	}
	
	n = cnt;
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = m; j >= v[i]; j--)
		{
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}
	
	cout << f[m] << "\n";
	
	return 0;
}
  • 单调队列
// Problem: 庆功会
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/1021/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int f[N], g[N], q[N];
int n, m, v, w, s;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	for(int i = 0; i < n ; i++)
	{
		cin >> v >> w >> s;
		memcpy(g, f, sizeof f);
		for(int j = 0; j < v; j++)
		{
			int hh = 0, tt = -1;
			
			for(int k = j; k <= m; k += v)
			{
				if(hh <= tt && q[hh] < k - s * v) hh++;
				while(hh <= tt && g[q[tt]] - q[tt] / v * w  <= g[k] - k / v * w) tt--;
				q[++tt] = k;
				f[k] = g[q[hh]] + (k - q[hh]) / v * w;
			}
		}
	}
	
	cout << f[m] << "\n";
	return 0;
}

混合背包问题

// Problem: 混合背包问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/7/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int f[N], w[N], v[N];
int cnt;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	auto solve =[&] ()
	{
		int n, m;
		cin >> n >> m;
		
		for(int i = 0; i < n; i++)
		{
			int a, b, s;
			cin >> a >> b >> s;
			if(s == 0) s = m / a;
			else if(s == -1) s = 1;
			
			int k = 1;
			while(k <= s)
			{
				cnt++;
				v[cnt] = k * a;
				w[cnt] = k * b;
				s -= k;
				k *= 2;
			} 
			
			if(s)
			{
				cnt++;
				v[cnt] = s * a;
				w[cnt] = s * b;
			}
			
		}
		
		n = cnt;
		for(int i = 1; i <= n; i++)
		{
			for(int j = m; j >= v[i]; j--)
			{
				f[j] = max(f[j], f[j - v[i]] + w[i]);
			}
		}
		
		cout << f[m] << "\n";
	};
	
	int t = 1;
	while(t--)
	{
		solve();
	}
	return 0;
}

二维费用的背包问题

// Problem: 二维费用的背包问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/8/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int f[N][N];
int n, V, M;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> V >> M;
	
	
	for(int i = 0; i < n; i++)
	{
		int v, m, w;
		cin >> v >> m >> w;
		for(int j = V; j >= v; j--)
		{
			for(int k = M; k >= m; k--)
			{
				f[j][k] = max(f[j][k], f[j - v][k - m] + w);
			}
		}
	}
	
	cout << f[V][M] << "\n";
	
	return 0;
}

潜水员

// Problem: 潜水员
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1022/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 22, M = 80;


int n, m, k;
int f[N][M];

	
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m >> k;
	memset(f, 127, sizeof f);
	
	f[0][0] = 0;
	for(int i = 0; i < k; i++)
	{
		int v1, v2, w;
		cin >> v1 >> v2 >> w;
		
		for(int i = n; ~i; i--)
		{
			for(int j = m; ~j; j--)
			{
				f[i][j] = min(f[i][j], f[max(0, i - v1)][max(0, j - v2)] + w);
			}
		}
	}	
	cout << f[n][m] << "\n";
	
	return 0;
}

机器分配

// Problem: 机器分配
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1015/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int n, m;
int f[N][N];
int w[N][N];
int path[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			cin >> w[i][j];
		}
	}
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			for(int k = 0; k <= j; k++)
			{
				f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
			}
		}
	}
	
	cout << f[n][m] << "\n";
	
	int j = m;
	
	for(int i = n; i; i--)
	{
		for(int k = 0; k <= j; k++)
		{
			if(f[i][j] == f[i - 1][j - k] + w[i][k])
			{
				path[i] = k;
				j -= k;
				break;
			}
		}
	}
	
	for(int i = 1; i <= n; i++) cout << i << " " << path[i] << "\n";
	
	
	return 0;
}

// Problem: 机器分配
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/1015/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

const int N = 20;

int n, m;
int w[N][N];
int f[N][N];
int path[N], cnt;

void dfs(int i, int j)
{
	if(!i) return;
	
	for(int a = 0; a <= j; a++)
	{
		if(f[i][j] == f[i - 1][j - a] + w[i][a])
		{
			path[cnt++] = a;
			dfs(i - 1, j - a);
			return;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			cin >> w[i][j];
		}
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			for(int k = 0; k <= j; k++)
			{
				f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
			}
		}
	}
	
	cout << f[n][m] << "\n";
	dfs(n, m);
	for(int i = cnt - 1, id = 1; ~i; i--, id++)
	{
		cout << id << " " << path[i] << "\n";
	}
	return 0;
}

开心的金明

// Problem: 开心的金明
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/428/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int n, m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	
	for(int i = 0; i < m; i++)
	{
		int v, w;
		cin >> v >> w;
		for(int j = n; j >= v; j--)
		{
			f[j] = max(f[j], f[j - v] + v * w);
		}
	}
	cout << f[n] << "\n";
	return 0;
}

有依赖的背包问题

// Problem: 有依赖的背包问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/10/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 110;

int n, m;
int v[N], w[N];
int h[N], e[N], ne[N], idx;

int f[N][N];

void add(int a, int b)
{
	e[idx] = b, ne[idx]= h[a], h[a] = idx++;
}


void dfs(int u)
{
	for(int i = h[u]; ~i; i = ne[i])
	{
		int son = e[i];
		dfs(e[i]);
		//分组背包，子树看为一个物品组。
		for(int j = m - v[u]; ~j; j--)
		{
			for(int k = 0; k <= j; k++)
			{
				f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
			}
		}
	}
	
	for(int i = m; i >= v[u]; i--) f[u][i] = f[u][i - v[u]] + w[u];
	//根节点体积都放不了，就为0
	for(int i = 0; i < v[u]; i++) f[u][i] = 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	memset(h, -1, sizeof h);
	cin >> n >> m;
	int root;
	for(int i = 1; i <= n; i++)
	{
		int p;
		cin >> v[i] >> w[i] >> p;
		if(p == -1) root = i;
		else add(p, i);
	}
	dfs(root);
	cout << f[root][m] << "\n";
	return 0;
}

背包问题求解方案数

// Problem: 背包问题求方案数
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/11/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;

int n, m;
int f[N], g[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	
	memset(f, 128, sizeof f);
	f[0] = 0;
	g[0] = 1;
	
	for(int i = 0; i < n; i++)
	{
		int v, w;
		cin >> v >> w;
		
		for(int j = m; j >= v; j--)
		{
			int maxv = max(f[j], f[j - v] + w);
			int s = 0;
			if(f[j] == maxv) s = g[j];
			if(f[j - v] + w == maxv) s = (s + g[j - v]) % mod;
			f[j] = maxv, g[j] = s;
		}
	}
	
	
	int res = 0;
	for(int i = 1; i <= m; i++)
	{
		if(f[i] > f[res])
		{
			res = i;
		}
	}
	
	int sum = 0;
	for(int i = 0; i <= m; i++)
	{
		if(f[i] == f[res])
		{
			sum = (sum + g[i]) % mod;
		}
	}
	
	cout << sum << "\n";
	
	return 0;
}

背包问题求具体方案

// Problem: 背包问题求具体方案
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/12/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		cin >> v[i] >> w[i];
	}
	//倒推，核心是要判断当前这一个是由上个状态的哪一形式转化而来。
	//字典序最小，必须要满足从前向后考虑，且对于只能选的点，必须选，对于不能选的点，必不选，对于可选可不选的点，一定要选
	//所谓dp求方案，相当于图论的最短路。
	//字典序最小，需要我们从前向后判断，所以dp就要倒推
	for(int i = n; i >= 1; i--)
	{
		for(int j = 0; j <= m; j++)
		{
			f[i][j] = f[i + 1][j];
			if(j >= v[i])
			{
				f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
			}
		}
	}
	
	
	int j = m;
	for(int i = 1; i<= n; i++)
	{
		if(j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
		{
			cout << i << " ";
			j -= v[i];
		}
	}
	
	return 0;
}

能量石（后续补）

金明的预算方案

// Problem: 金明的预算方案
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/489/
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define v first
#define w second

typedef pair<int, int> PII;

const int N = 60, M = 32010;

int n, m;
PII master[N];
vector<PII> servent[N];

int f[M];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> m >> n;
	for(int i = 1;i <= n; i++)
	{
		int v, p, q;
		cin >> v >> p >> q;
		
		p *= v;
		if(!q) master[i] = {v, p};
		else servent[q].push_back({v, p});
	}
	
	
	for(int i = 1; i <= n; i++)
	{
		for(int u = m; u >= 0; u--)
		{
			for(int j = 0; j < 1 << servent[i].size(); j++)
			{
				int v = master[i].v, w = master[i].w;
				
				for(int k = 0; k < servent[i].size();k++)
				{
					if(j >> k & 1)
					{
						v += servent[i][k].v;
						w += servent[i][k].w;
					}
				}
				if(u >= v) f[u] = max(f[u], f[u - v] + w);
			}
		}
	}
	
	cout << f[m] << "\n";
	return 0;
}