招商网站平台,最强大的wordpress,网站代更新,wordpress 连接信息文章目录 1、摆花2、异或选数3、数字三角形 1、摆花 分析#xff1a; 输入2 4 3 2 的情况下#xff0c;只有 (2,2) , (3,1) 这两种方案。 所以#xff0c;设置状态 dp[i][j] 表示到第 i 种花#xff08;共 n 种花#xff09;、第 j 个位置#xff08;共 m 个位置#xf… 文章目录 1、摆花2、异或选数3、数字三角形 1、摆花 分析 输入2 4 3 2 的情况下只有 (2,2) , (3,1) 这两种方案。 所以设置状态 dp[i][j] 表示到第 i 种花共 n 种花、第 j 个位置共 m 个位置的情况下的总方案数。 k 表示 第 i 种花使用的数量a[i] 表示第 i 种花本来的数量。
示例代码
#includebits/stdc.h
using namespace std;
using ll long long;
const ll p 1e67 , N 1e35;
ll a[N],dp[N][N];
int n,m;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinnm;for(int i1;in;i)cina[i];dp[0][0]1;for(int i1;in;i){for(int j0;jm;j){for(int k0;ka[i]kj;k)// kj 避免花数过多超过了j余下的位置dp[i][j](dp[i][j]dp[i-1][j-k])%p;}}coutdp[n][m];return 0;
}2、异或选数 分析 有多少个子序列进行异或可以得到x。 设状态 dp[i][j] 表示到第 i 个数字共n个、异或和为 j 的子序列的个数。 对于每次的状态有选择这个数 和 不选择 这两种情况。 dp[i][j] dp[i-1][j] dp[i-1][j^a[i]]
代码示例
#includebits/stdc.h
using namespace std;
const int N 1e55,p 998244353;
int a[N],dp[N][70],n,x;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinnx;for(int i1;in;i)cina[i];dp[0][0]1;for(int i1;in;i){for(int j0;j64;j){//a[i]63所以异或结果肯定不会大于64dp[i][j](dp[i-1][j]dp[i-1][j^a[i]])%p;}}coutdp[n][x];return 0;
}3、数字三角形 分析
设置 dp[i][j][k] 表示从ij出发一共进行了 k 次右移,n-i-k次左移。 dp[i][j][k] a[i][j] max(dp[i1][j][k],dp[i1][j1][k-1])
代码示例
#includebits/stdc.h
using namespace std;
const int N 1e25;
int a[N][N],dp[N][N][N];
int n;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinn;for(int i1;in;i)for(int j1;ji;j)cina[i][j];for(int in;i1;i--){for(int j1;ji;j){for(int k0;kn-i;k){if(k1)dp[i][j][k]a[i][j]max(dp[i1][j][k],dp[i1][j1][k-1]);else dp[i][j][k]a[i][j]dp[i1][j][k];}}}if(n1)coutdp[1][1][(n-1)/2];else coutmax(dp[1][1][(n-1)/2],dp[1][1][n-1-(n-1)/2]); return 0;
}DFS暴力解决只能过50%oi赛制的蓝桥杯还是能骗分的如果用dp的话可能根本就想不到
#includebits/stdc.h
using namespace std;
const int N 1e35;
int a[N][N],note[N];
int n;
int maxsum;
void dfs(int x,int left,int right){if(xn){if(abs(left-right)1)return;note[x]a[x][1right];// 第 x 个 int sum0;for(int i1;in;i)sumnote[i]; if(summaxsum)maxsumsum;return;}note[x]a[x][right1];// 第x行第right1个 dfs(x1,left1,right);// 向下移动 left1 dfs(x1,left,right1);// 向左移动 right1
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinn;for(int i1;in;i)for(int j1;ji;j)cina[i][j];dfs(1,0,0);coutmaxsum; return 0;
}
