首页 > 分享 > 洛谷题单指南

洛谷题单指南

花匠小妙招
2024-11-15 23:23

原题链接：https://www.luogu.com.cn/problem/P1854

题意解读：F束花依次放入V个花瓶，每个花瓶最多一朵，且花的顺序在花瓶中递增，计算最大的美学值，并且输出每朵花具体放置方案。

解题思路：

首先想到的的DFS法，对于每一朵花，枚举所有的摆放方案，累加美学值，并记录放置位置，完成一种方案就记录最大美学值和对应的摆放位置。

尽管知道会超时，先拿到部分分再说！

19分代码-DFS：

#include <bits/stdc++.h> using namespace std; const int N = 105; int f, v; int a[N][N]; int b[N]; //一个方案 int maxx = -2e9, ans[N]; //最大美学值，ans是最大美学值情况下每一朵花的方案 //考察第x朵花，前x-1朵花的美学值之和为sum void dfs(int x, int sum) { if(x > f) { if(sum > maxx) { maxx = sum; for(int i = 1; i <= f; i++) ans[i] = b[i]; //将b的方案拷贝到ans } return; } for(int i = b[x-1] + 1; i <= v; i++) //枚举第x朵花可以放置的花瓶，从第x-1朵花放置的花瓶数+1开始 { b[x] = i; //把第x朵花放入i花瓶 dfs(x + 1, sum + a[x][i]); b[x] = 0; //回溯 } } int main() { cin >> f >> v; for(int i = 1; i <= f; i++) for(int j = 1; j <= v; j++) cin >> a[i][j]; dfs(1, 0); cout << maxx << endl; for(int i = 1; i <= f; i++) cout << ans[i] << " "; return 0; }

如何对DFS代码进行优化，想到了记忆化搜索+剪枝，这里有一个特点：

对于每一朵花，枚举放置的位置一定是越来越靠后，而每朵花前面放置时的美学值如果比后面放置时的美学值大，那么后面的dfs可以提前结束，

因为再考察下去也无法得到最大美学值。

因此，可以记录mem[第x朵花][第x-1朵花的花瓶] = 考察第x朵花且已知第x-1朵花放置的花瓶时的美学值之和

100分代码-DFS+记忆化+剪枝：

#include <bits/stdc++.h> using namespace std; const int N = 105; int f, v; int a[N][N]; int b[N]; //一个方案 int mem[N][N]; //mem[i][j]记录第i朵花，第i-1朵花放置的花瓶是j时的美学值之和 int maxx = -0x3f3f3f3f, ans[N]; //最大美学值，ans是最大美学值情况下每一朵花的方案 //考察第x朵花，前x-1朵花的美学值之和为sum void dfs(int x, int sum) { if(sum <= mem[x][b[x-1]]) return; //如果当前sum比之前记录的要小或相等，不用继续dfs，提前结束 mem[x][b[x-1]] = sum; //记录第x朵花第x-1花放置的花瓶位置对应的美学值之和 if(x > f) { if(sum > maxx) { maxx = sum; for(int i = 1; i <= f; i++) ans[i] = b[i]; //将b的方案拷贝到ans } return; } for(int i = b[x-1] + 1; i <= v; i++) //枚举第x朵花可以放置的花瓶，从第x-1朵花放置的花瓶数+1开始 { b[x] = i; //把第x朵花放入i花瓶 dfs(x + 1, sum + a[x][i]); b[x] = 0; //回溯 } } int main() { cin >> f >> v; for(int i = 1; i <= f; i++) for(int j = 1; j <= v; j++) cin >> a[i][j]; memset(mem, -0x3f, sizeof(mem)); dfs(1, 0); cout << maxx << endl; for(int i = 1; i <= f; i++) cout << ans[i] << " "; return 0; }

本题正解应该是动态规划，

设dp[i][j]表示前i朵花放入前j个花瓶的最大美学值, a[i][j]是第i朵花放入j号花瓶的美学值

当i放入j：dp[i][j] = dp[i-1][j-1] + a[i][j]

当i不放入j：dp[i][j] = dp[i-1][j]

因此：dp[i][j] = max(dp[]i-1[j], dp[i-1][j-1] + a[i][j])

初始化：

由于有负数，dp初始化为负无穷，memset(dp, -0x3f, sizeof(dp))；且dp[0][j] = 0，前0朵花的美学值是0。

结果：dp[f][v]

记录具体方案:

用 struct node {

vector<int> a;

} ans[i][j] 记录前i朵花放入前j个花瓶得到最大美学值时的放置方案，

将转移方程dp[i][j] = max(dp[i][j-1], dp[i-1][j-1] + a[i][j])拆分为if...else...来分情况处理，记录放置方案的更新和转移，具体参考代码：

100分代码-动态规划：

#include <bits/stdc++.h> using namespace std; const int N = 105; int f, v; int a[N][N]; int dp[N][N]; //dp[i][j]表示前i朵花放入前j个花瓶的最大美学值 struct node { vector<int> a; } ans[N][N]; //ans[i][j]记录前i朵花放入前j个花瓶得到最大美学值时的放置方案 int main() { cin >> f >> v; for(int i = 1; i <= f; i++) for(int j = 1; j <= v; j++) cin >> a[i][j]; memset(dp, -0x3f, sizeof(dp)); //初始化 for(int j = 0; j <= v; j++) dp[0][j] = 0; //0朵花放j个花瓶的美学值是0 for(int i = 1; i <= f; i++) { for(int j = i; j <= v; j++) //花瓶号不可能小于花的编号 { if(dp[i-1][j-1] + a[i][j] > dp[i][j-1]) //第i朵花放第j个花瓶 { dp[i][j] = dp[i-1][j-1] + a[i][j]; //把i-1,j-1的方案拷贝到i,j的方案 for(int v : ans[i-1][j-1].a) { ans[i][j].a.push_back(v); } //i，j的方案再加上i放入第j个花瓶 ans[i][j].a.push_back(j); } else //第i朵花不放第j个花瓶 { dp[i][j] = dp[i][j-1]; //把i,j-1的方案拷贝到i,j的方案 for(int v : ans[i][j-1].a) { ans[i][j].a.push_back(v); } } } } cout << dp[f][v] << endl; for(int v : ans[f][v].a) cout << v << " "; return 0; }