DP问题汇总--->适配于蓝桥杯省赛

作者： 作者的头像   YMYS ,  2025-04-11 16:25:56 · 河南 ,  所有人可见 ,  阅读 27

0


有几道题没有完成，省赛过后完善

作者信息

/*
 * @Author: YMYS
 * @Date: 2025-04-07 10:36:24
 * @LastEditTime: 2025-04-07 18:10:07
 * @FilePath: \VScode-C&C++-Coding\Acwing\算法基础课\5.第五章\DP问题总结.cpp
 * @URL:https://www.acwing.com/file_system/file/content/whole/index/content/13349550/
 * @Description: 
 */

一、数字三角形模型

/*
    一、数字三角形模型

    我们发现数字三角形模型就是在路径上只能二选一，然后最后择出最优
    我们建立模型只需从末尾开始往前遍历即可

*/

1.1、数字三角形

// //1.1、数字三角形
////https://www.acwing.com/problem/content/900/
// #include<bits/stdc++.h>

// #define int long long
// #define err cout << "error" << endl

// using namespace std;

// const int N = 510;

// // int T;
// // void solve(){

// // }

// int n;
// int w[N][N];
// int dp[N][N];

// signed main()
// {
// #ifdef ABC
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
//     std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);

//     // cin>>T;
//     // while(T--){
//     //     solve();
//     // }
//     cin>>n;

//     for(int i=1;i<=n;i++){
//         for(int j=1;j<=i;j++) {
//             cin>>w[i][j];
//             if(i==n){
//                 dp[i][j] = w[i][j];
//             }
//         }
//     }

//     for(int i=n-1;i>=1;i--){
//         for(int j=1;j<=i;j++){
//             dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + w[i][j];
//         }
//     }

//     cout<<dp[1][1]<<endl;

//     return 0;
// }

1.2、摘花生

// //1.2、摘花生
////https://www.acwing.com/problem/content/1017/
// #include<bits/stdc++.h>

// #define int long long
// #define err cout << "error" << endl

// using namespace std;

// const int N = 110;

// int r,c;
// int w[N][N];
// int dp[N][N];

// int T;
// void solve(){
//     cin>>r>>c;
//     for(int i=1;i<=r;i++){
//         for(int j=1;j<=c;j++){
//             cin>>w[i][j];
//         }
//     }


//     dp[1][1] = w[1][1];
//     for(int i=2;i<=r;i++) dp[i][1] = dp[i-1][1] + w[i][1];
//     for(int i=2;i<=c;i++) dp[1][i] = dp[1][i-1] + w[1][i];

//     for(int i=2;i<=r;i++){
//         for(int j=2;j<=c;j++){
//             dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + w[i][j];
//         }
//     }

//     cout<<dp[r][c]<<endl;
// }

// signed main()
// {
// #ifdef ABC
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
//     std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);

//     cin>>T;
//     while(T--){
//         solve();
//     }



//     return 0;
// }

1.3、最低通行费

// //1.3、最低通行费
// //https://www.acwing.com/problem/content/1020/
// #include<bits/stdc++.h>

// #define int long long
// #define err cout << "error" << endl

// using namespace std;

// const int N = 110;

// // int T;
// // void solve(){

// // }

// int n;
// int w[N][N];
// int dp[N][N];

// signed main()
// {
// #ifdef ABC
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
//     std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);

//     // cin>>T;
//     // while(T--){
//     //     solve();
//     // }
//     cin>>n;
//     for(int i=1;i<=n;i++){
//         for(int j=1;j<=n;j++){
//             cin>>w[i][j];
//         }
//     }

//     dp[1][1] = w[1][1];
//     for(int i=2;i<=n;i++) dp[i][1] = dp[i-1][1] + w[i][1];
//     for(int i=2;i<=n;i++) dp[1][i] = dp[1][i-1] + w[1][i];

//     for(int i=2;i<=n;i++){
//         for(int j=2;j<=n;j++){
//             dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + w[i][j];
//         }
//     }

//     cout<<dp[n][n]<<endl;

//     return 0;
// }

1.4、方格取数

//【国赛再来写这道题】
// //1.4、方格取数
// //https://www.acwing.com/problem/content/1029/
//不能分两次走，因为两次都是局部最优，不能保证全局最优
// #include<bits/stdc++.h>

// #define int long long
// #define err cout << "error" << endl

// using namespace std;

// const int N = 15;

// int n;
// int w[N][N];
// int dp[N][N];
// int sum;

// // int T;
// // void solve(){

// // }

// signed main()
// {
// #ifdef ABC
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
//     std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);

//     // cin>>T;
//     // while(T--){
//     //     solve();
//     // }

//     cin>>n;
//     int x,y,z;
//     while (cin>>x>>y>>z)
//     {
//         cin>>x>>y>>z;
//         if(x==y==z==0) break;
//         w[x][y] = z;
//     }



//     return 0;
// }

1.5、传纸条


//1.5、传纸条

二、线性DP–>最长上升子序列模型

/*
    二、线性DP-->最长上升子序列模型
*/
///////////////////////////////////////////省赛版本/////////////////////////////////////////////

2.1.1、最长上升子序列（暴力DP版本）

// //2.1.1、最长上升子序列（暴力DP版本）
// //https://www.acwing.com/problem/content/description/897/
// #include<bits/stdc++.h>

// #define int long long
// #define err cout << "error" << endl

// using namespace std;

// const int N = 1100;

// // int T;
// // void solve(){

// // }

// int n;
// int a[N];//原始的值
// int b[N];//b[i]表示以a[i]结尾的最长上升子序列的长度

// signed main()
// {
// #ifdef ABC
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
//     std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);

//     // cin>>T;
//     // while(T--){
//     //     solve();
//     // }
//     cin>>n;
//     for(int i=1;i<=n;i++){
//         cin>>a[i];
//     }

//     for(int i=1;i<=n;i++){
//         b[i] = 1;

//         for(int j=1;j<i;j++){
//             if(a[j] < a[i]){
//                 b[i] = max(b[i], b[j]+1);
//             }
//         }
//     }

//     int res = 1;
//     for(int i=1;i<=n;i++){
//         res = max(res, b[i]);
//     }

//     cout<<res<<endl;

//     return 0;
// }

2.1.2、最长上升子序列2（优化贪心版本）



// //2.1.2、最长上升子序列2（优化贪心版本）
// //https://www.acwing.com/problem/content/898/
// #include<bits/stdc++.h>

// #define int long long
// #define err cout << "error" << endl

// using namespace std;

// const int N = 1e5 +10;

// // int T;
// // void solve(){

// // }

// int n;
// int a[N];
// vector<int> b;

// signed main()
// {
// #ifdef ABC
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
//     std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);

//     // cin>>T;
//     // while(T--){
//     //     solve();
//     // }
//     cin>>n;
//     for(int i=1;i<=n;i++) cin>>a[i];

//     b.push_back(a[1]);
//     for(int i=2;i<=n;i++){
//         int mx = b.back();

//         if(mx>=a[i]){
//             auto id = lower_bound(b.begin(), b.end(), a[i]);

//             *id = a[i];
//         }else{
//             b.push_back(a[i]);
//         }
//     }

//     cout<<b.size()<<endl;

//     return 0;
// }

2.1.3、最长公共子序列


// //2.1.3、最长公共子序列
// //https://www.acwing.com/problem/content/899/
// #include<bits/stdc++.h>

// #define int long long
// #define err cout << "error" << endl

// using namespace std;

// //数据范围是1e3，直接开两层for循环又如何，开个二维数组疯狂遍历
// const int N = 1010;

// // int T;
// // void solve(){

// // }

// int n,m;
// char s1[N],s2[N];
// int p[N][N];

// signed main()
// {
// #ifdef ABC
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
//     std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);

//     // cin>>T;
//     // while(T--){
//     //     solve();
//     // }

//     cin>>n>>m>>s1+1>>s2+1;
//     for(int i=1;i<=n;i++){
//         for(int j=1;j<=m;j++){
//             p[i][j] = max(p[i-1][j], p[i][j-1]);//DP的特点，两个都选取最优值

//             if(s1[i]==s2[j]) p[i][j] = max(p[i][j], p[i-1][j-1] + 1);
//         }
//     }

//     cout<<p[n][m]<<endl;

//     return 0;
// }

2.1.4、接龙数列

//2.1.4、接龙数列
//https://www.acwing.com/problem/content/4961/
//本质上也是最长上升子序列，就是check函数不同
/*
 * @Author: YMYS
 * @Date: 2025-04-06 22:25:05
 * @LastEditTime: 2025-04-07 21:24:46
 * @FilePath: \VScode-C&C++-Coding\蓝桥杯真题\第14届-2023\省赛\5.接龙数列2.cpp
 * @URL:https://www.acwing.com/problem/content/4961/
 * @Description: 4958. 接龙数列
 * 
 * 我们一定要记住！！！！DP的优化是怎么优化的！！！！！！！
 * 
 */
 ```

 暴力版本

 ```
// //第一眼最长上升子序列，只是改一下check()函数而已
// //暴力过：7/115
// #include<bits/stdc++.h>

// #define int long long
// #define err cout << "error" << endl

// using namespace std;

// const int N = 1e5 +10;

// // int T;
// // void solve(){

// // }

// int n;
// string a[N];
// int dp[N];

// signed main()
// {
// #ifdef ABC
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
//     std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);

//     // cin>>T;
//     // while(T--){
//     //     solve();
//     // }
//     cin>>n;
//     for(int i=1;i<=n;i++) cin>>a[i];

//     for(int i=1;i<=n;i++){
//         dp[i] = 1;
//         for(int j=1;j<i;j++){
//             if(a[j][a[j].size()-1] == a[i][0]) dp[i] = max(dp[i], dp[j]+1);
//         }
//     }

//     int sum = 0;
//     for(int i=1;i<=n;i++) sum = max(sum, dp[i]);

//     cout<<n-sum<<endl;


//     return 0;
// }

优化版本

// //优化版本
// //对于被优化的部分，我将会注释掉
// #include<bits/stdc++.h>

// #define int long long
// #define err cout << "error" << endl

// using namespace std;

// const int N = 1e5 + 10;

// int n;
// string a[N];
// int dp[N];
// int cnt[15];//cnt[i]：表示以数字i结尾的所有【序列】与【子序列】个数中，最长的子序列的个数是多少

// signed main()
// {
// #ifdef ABC
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
//     freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
//     std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);

//     cin>>n;
//     for(int i=1;i<=n;i++) cin>>a[i];

//     for(int i=1;i<=n;i++){
//         dp[i] = 1;

//         //注意看这部分
//         //我们发现i是固定的，也就是说a[i][0]是固定的，
//         //我们调用这一层的循环都是在寻找整个a[]数组是否存在一个定数
//         //那这样的话我们为什么不可以提前把这个数统计一下然后记下来呢？
//         // for(int j=1;j<i;j++){
//         //     if(a[j][a[j].size()-1] == a[i][0]) dp[i] = max(dp[i], dp[j]+1);
//         // }

//         //我们现在遍历的是第i个数
//         //第i个数最左边的char，拿来替代第 k(k<i) 个数最右边的char
//         int it = a[i][0] - '0';
//         dp[i] = max(dp[i], cnt[it]+1);

//         //更新
//         int &is = cnt[a[i][a[i].size()-1] - '0'];
//         is = max(is, dp[i]);
//     }

//     int sum = 0;
//     for(int i=1;i<=n;i++) sum = max(sum, dp[i]);

//     cout<<n-sum<<endl;

//     return 0;
// }

2.1.5、最短编辑距离


//2.1.5、最短编辑距离
//https://www.acwing.com/problem/content/904/

2.1.6、编辑距离


//2.1.6、编辑距离
//https://www.acwing.com/problem/content/901/



///////////////////////////////////////////国赛版本/////////////////////////////////////////////////////
//2.2.1、

三、背包模型


/*
    三、背包模型
*/

四、区间DP

/*
    四、区间DP
*/
///////////////////////////////////////////省赛版本/////////////////////////////////////////////

4.1.1、石子合并

//4.1.1、石子合并
//https://www.acwing.com/problem/content/284/

///////////////////////////////////////////国赛版本/////////////////////////////////////////////////////

4.2.1、环形石子合并

//4.2.1、环形石子合并
//https://www.acwing.com/problem/content/1070/

4.2.2、能量项链


//4.2.2、能量项链
//https://www.acwing.com/problem/content/322/

4.2.3、加分二叉树


//4.2.3、加分二叉树
//https://www.acwing.com/problem/content/481/

4.2.4、凸多边形的划分


//4.2.4、凸多边形的划分
//https://www.acwing.com/problem/content/1071/

4.2.5、棋盘分割


//4.2.5、棋盘分割
//https://www.acwing.com/problem/content/323/

//-----------------------------------------------------------------------------------------------------------------------------------------

五、数位DP

/*
    五、数位DP 
*/

0 评论

1024
x