搜索+动态规划

刷题刷题刷题刷题

​​​​​​​​​​​​​​Forgery - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

需要两个数组，一个数组全部初始化为".",另一个数组输入数据，每碰到一个“.”就进行染色操作，将其周围的8个全部变成"#",全部染完色之后将两个数组进行比对，若完全一样则YES,否则NO

AC代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{int k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}
char a[1010][1010];
char b[1010][1010];
int n, m;
int flag;
bool cmp()
{for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)if (a[i][j] != b[i][j])return false;return true;
}
void dfs(int x, int y)
{flag = 1;int next[8][2] = { {1,1},{-1,-1},{-1,0},{1,0},{0,1},{0,-1},{1,-1},{-1,1} };for (int i = 0; i < 8; i++){int tx = x + next[i][0];int ty = y + next[i][1];if (tx<1 || ty<1 || tx>n || ty>m){flag = 0;return;}if (a[tx][ty] != '#'){flag = 0;break;}}if (!flag)return;for (int i = 0; i < 8; i++){int tx = x + next[i][0];int ty = y + next[i][1];b[tx][ty] = '#';}
}
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 >> a[i][j];b[i][j] = '.';}for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++){dfs(i, j);}if (cmp())cout << "YES";else{cout << "NO";}return 0;
}

P1460 [USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

开始没写出来，看了题解后有了一些头绪（感觉应该有普及+的难度了）。

用数组记录需要种类数的最小量和不同饲料不同种类的最小量，

从第一种饲料开始进入搜索，每次搜索进行一次判断，若饲料数已超过数据则马上结束这一次搜索（对当前饲料进行搜索，用数组记录），得到需要的饲料数，并用数组存起来所需的饲料编号，对所有饲料的相同一种的维他命进行判断，得到最优解，继续进行搜索有两种可能（一是不算当前饲料，即饲料数加1，但是所需饲料数不加1，二是当前饲料数和所需饲料数都加1），最后所有搜索结束后按照题目要求输出即可

AC：

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{int k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}
int a[1010];
int b[1010][1010];
int ans[1010];
int n, m, k=20;
int s[1010];
bool judge(int x)
{for (int i = 1; i <= n; i++){int sum = 0;for (int j = 1; j <= x; j++){sum += b[s[j]][i];}if (sum < a[i])return false;}return true;
}
void dfs(int pos, int num)
{if (pos > m){if (judge(num) && num < k){k = num;for (int i = 1; i <=  num; i++){ans[i] = s[i];}}return;}s[num + 1] = pos;dfs(pos + 1, num + 1);dfs(pos + 1, num);
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}cin >> m;for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){cin >> b[i][j];}}dfs(1, 0);cout << k << " ";for (int i = 1; i <= k; i++)cout << ans[i] << " ";cout << endl;return 0;
}

01背包思路（太久远了，忘了）

来几道板子题唤醒一下沉睡的记忆

P1060 [NOIP2006 普及组] 开心的金明 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

AC：

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{int k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}
int v[100010], w[100010];
int dp[1010][30010];
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;for (int i = 1; i <= m; i++){cin >> v[i] >> w[i];w[i] = w[i] * v[i];}for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){if (v[i] > j){dp[i][j] = dp[i - 1][j];}else{dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);}}}cout << dp[m][n];return 0;
}

P1049 [NOIP2001 普及组] 装箱问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

AC：

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{int k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}
int dp[35][20010];
int w[20010];
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int v, n;cin >> v >> n;for (int i = 1; i <= n; i++){cin >> w[i];}for (int i = 1; i <= n; i++){for (int j = 1; j <= v; j++){if (w[i] > j){dp[i][j] = dp[i - 1][j];}else{dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]]+w[i]);}}}cout << v-dp[n][v];return 0;
}

P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{int k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}
int w[110];
int t[1100];
int dp[110][1100];
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;for (int i = 1; i <= m; i++){cin >> t[i] >> w[i];}for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){if (t[i] > j)dp[i][j] = dp[i - 1][j];else{dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - t[i]] + w[i]);}}}cout << dp[m][n];return 0;
}

分组背包问题（卡了半天也并不知道哪错了，无语）

P1757 通天之分组背包 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
inline int read()
{int k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}
int a[1010], b[1010], c[1010];
int dp[1010];
int g[1010][1010];
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, t, x = 0;cin >> m >> n;for (int i = 1; i <= n; i++){cin >> a[i] >> b[i] >> t;x = max(t, x);c[t]++;g[t][c[t]] = i;}for (int i = 1; i <= x; i++)//小组{for (int j = m; j >= 0; j--)//容量{for (int k = 1; k <= c[i]; k++)//小组成员{if(a[g[i][k]]<=j)dp[j] = max(dp[j], dp[j - a[g[i][k]]] + b[g[i][k]]);}}}cout << dp[m] << endl;return 0;
}