【蓝桥杯专题】 DP（C++ | 洛谷 | acwing | 蓝桥）

菜狗现在才开始备战蓝桥杯QAQ

【蓝桥杯专题】 DP（C++ | 洛谷 | 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 <algorithm>using 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 cout<<"debug"<<"\n"
#define endl "\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
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 cout<<"debug"<<"\n"
#define endl "\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
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 cout<<"debug"<<"\n"
#define endl "\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
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 多刷 （大部分题型）