可以提前看看900. 整数划分 - AcWing题库
（好像只有买过算法基础课才能看）里面有划分标准——闫氏dp分析法
会不断更新
建议参考这篇题解AcWing 4181. 数的划分——最全解法 - AcWing
🎆🎆🎆🎆🎆🎆
P1025 [NOIP2001 提高组] 数的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
注意看f[i,j]的含义
#include <iostream> using namespace std; const int N = 210, M = 10; int f[N][M]; int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, k; cin >> n >> k; f[0][0] = 1; for (int i = 1; i <= n; i ++) f[i][1] = 1;//注意看f[i,j]的含义 for (int i = 1; i <= n; i ++) for (int j = 2; j <= min(i, k); j ++)//从2开始 f[i][j] = f[i - 1][j - 1] + f[i - j][j]; cout << f[n][k] << endl; return 0; }
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 310; int n,m; //网格滑雪场的行和列 int f[N][N]; //状态转移式 int h[N][N]; //网格滑雪场 int dx[4] = {-1,0,1,0}; int dy[4] = {0,1,0,-1}; int dp(int x,int y){ int &v = f[x][y]; //Y总说的小技巧，等于把f[x][y]简化成了v，如果v发生变化，f[x][y]也会随之变化 if(v != -1) return v; //如果已经计算过了，就可以直接返回答案 v = 1; //注意v要先赋值为1哦~ for(int i = 0;i < 4;i ++){ //四个方向 int xx = x + dx[i]; int yy = y + dy[i]; if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && h[x][y] > h[xx][yy]){ //判断这点是否能走 v = max(v,dp(xx,yy) + 1); //更新 } } return v; //别忘了返回v啊（被坑了 } int main(){ cin>>n>>m; //输入滑雪场行和列 for(int i = 1;i <= n;i ++){ for(int j = 1;j <= m;j ++){ cin>>h[i][j]; //读入滑雪场数据 } } memset(f,-1,sizeof f); int res = 0; //最后答案 for(int i = 1;i <= n;i ++){ for(int j = 1;j <= m;j ++){ //因为这个人可以在任意一点开始滑，所以要遍历一遍滑雪场 res = max(res,dp(i,j)); //更新答案 } } cout<<res<<endl; return 0; }
看到这个题，我一开始没有想到是用dp来写，但是看到那个“最多”，就知道用dp了
#include<iostream> using namespace std; const int N = 105; int a[N][N], f[N][N]; int q, row, col; int main() { cin >> q; while(q--){ cin >> row >> col; for(int i = 1; i <= row; i++){ for(int j = 1; j <= col; j++){ cin >> a[i][j]; } } // f[i][j]指的是到(i, j)的最大花生数 for(int i = 1; i <= row; i++){ for(int j = 1; j <= col; j++){ f[i][j] = max(f[i-1][j], f[i][j-1]) + a[i][j]; } } cout << f[row][col] << endl; } return 0; }
Code over！
