三网合一 做网站,黑龙江省住房和城乡建设网站,兰州网络推广做啥的,新型塑料建筑模板图片菜狗现在才开始备战蓝桥杯QAQ 文章目录【蓝桥杯专题】 DP#xff08;C | 洛谷 | acwing | 蓝桥#xff09;AcWing 1205. 买不到的数目Acwing 1216. 饮料换购【模拟】01背包271. 杨老师的照相排列最长公共上升子序列PPPPPPPP总结【蓝桥杯专题】 DP#xff08;C | 洛谷 | acwi… 菜狗现在才开始备战蓝桥杯QAQ 文章目录【蓝桥杯专题】 DPC | 洛谷 | acwing | 蓝桥AcWing 1205. 买不到的数目Acwing 1216. 饮料换购【模拟】01背包271. 杨老师的照相排列最长公共上升子序列PPPPPPPP总结【蓝桥杯专题】 DPC | 洛谷 | acwing | 蓝桥
看最后总结
AcWing 1205. 买不到的数目
链接 链接
思路 暴力打表 找规律
#include iostream
using namespace std;int main () {int p, q;cin p q;cout ((p - 1) * (q - 1) - 1) endl;return 0;
}
Acwing 1216. 饮料换购【模拟】
链接 链接
#include iostream
#include cstring
#include algorithmusing namespace std;int main()
{int n, ans ;cin n; ans n;while((n / 3) 1) {// cout n endl;int t n / 3;ans t;n % 3 ;n t;}cout ans endl;
}01背包
链接 链接
#include bits/stdc.h
// #include iostream
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i a; i n; i )
#define per(i, a, n) for(int i n; i a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include stdlib.h // atoi
#define debug coutdebug\n
#define endl \n;
const int INF 0x3f3f3f3f;
const int mod1e97;
const int N 1010;int w[N], v[N];
int f[N][N];void solve () {int N, V;ll ans 0;cin N V;rep(i, 1, N) {cin v[i] w[i];}
// 当前背包容量不够j v[i]没得选因此前 i 个物品最优解即为前 i−1个物品最优解f[i][j] f[i - 1][j]。
// 如果可以选 f[i][j] f[i - 1][j - v[i]] w[i]。rep(i, 1, N) { rep(j, 1, V) {if(j v[i]) f[i][j] f[i - 1][j];else f[i][j] max(f[i - 1][j], f[i - 1][j - v[i]] w[i]);}}cout f[N][V] endl;
}int main(void){freopen(in.txt,r,stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T 1;// cin T;while(T --) solve();return 0;
}
271. 杨老师的照相排列
链接 链接 #include bits/stdc.h
// #include iostream
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i a; i n; i )
#define per(i, a, n) for(int i n; i a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include stdlib.h // atoi
#define debug coutdebug\n
#define endl \n;
const int INF 0x3f3f3f3f;
const int mod1e97;
const int N 31;ll f[N][N][N][N][N];void solve () {int n;while(cin n , n) {int s[5] {0};rep(i, 0, n - 1) cin s[i];memset(f, 0 , sizeof f);f[0][0][0][0][0] 1; rep(a, 0, s[0]) {rep(b, 0, min(s[1], a)) {rep(c, 0, min(s[2], b)) {rep(d, 0, min(s[3], c)) {rep(e, 0, min(s[4], d)) {// f[a][b][c][d][e]代表从后往前每排人数分别为a, b, c, d, e的所有方案的集合, 其中a b c d e 逆序的
// f[a][b][c][d][e]的值是该集合中元素的数量ll x f[a][b][c][d][e];if (a a - 1 b) x f[a - 1][b][c][d][e];if (b b - 1 c) x f[a][b - 1][c][d][e];if (c c - 1 d) x f[a][b][c - 1][d][e];if (d d - 1 e) x f[a][b][c][d - 1][e];if (e) x f[a][b][c][d][e - 1];// 当a 0 a - 1 b时最后一个同学可能被安排在第1排方案数是f[a - 1][b][c][d][e]
// 当b 0 b - 1 c时最后一个同学可能被安排在第2排方案数是f[a][b - 1][c][d][e]
// 当c 0 c - 1 d时最后一个同学可能被安排在第3排方案数是f[a][b][c - 1][d][e]
// 当d 0 d - 1 e时最后一个同学可能被安排在第4排方案数是f[a][b][c][d - 1][e]
// 当e 0时最后一个同学可能被安排在第5排方案数是f[a][b][c][d][e - 1]} }}}}cout f[s[0]][s[1]][s[2]][s[3]][s[4]] endl;}}int main(void){freopen(in.txt,r,stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T 1;// cin T;while(T --) solve();return 0;
}最长公共上升子序列
链接 链接
#include bits/stdc.h
// #include iostream
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i a; i n; i )
#define per(i, a, n) for(int i n; i a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include stdlib.h // atoi
#define debug coutdebug\n
#define endl \n;
const int INF 0x3f3f3f3f;
const int mod1e97;
const int N 3111;int a[N], b[N];
int f[N][N];void solve () {int n ;cin n;rep(i, 1, n) cin a[i];rep(i, 1, n) cin b[i];//版本1// rep(i, 1, n) {// rep(j, 1 , n) {// f[i][j] f[i - 1][j];// if(a[i] b[j]) {// // int maxv 1; // O(n^ 3)// // for(int k 1; k j; k ) {// // if(b[j] b[k]) {// // maxv max(maxv, f[i - 1][k] 1);// // }// // f[i][j] max(maxv, f[i][j]);// // }// }// }// }//版本2: rep(i, 1, n) {int maxv 1;rep(j, 1, n) {f[i][j] f[i - 1][j];if(a[i] b[j] ) f[i][j] max(maxv, f[i][j]);if(a[i] b[j]) maxv max(maxv, f[i - 1][j] 1);}}int res 0;rep(i, 1, n) {res max(res, f[n][i]);}cout res endl;}int main(void){freopen(in.txt,r,stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T 1;// cin T;while(T --) solve();return 0;
}# P
[链接 链接]( )P
链接 链接 P
链接 链接 P
链接 链接 P
链接 链接 P
链接 链接 P
链接 链接 P
链接 链接 P
链接 链接 总结
数论别浪费太多时间 做法暴力打表找规律 能做出来就做exit(0) 调试bug 针对没有输出的时候好用DP 多刷 大部分题型
