博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Codeforces-118D. Caesar's Legions(lazy dynamics)
阅读量:7286 次
发布时间:2019-06-30

本文共 1010 字,大约阅读时间需要 3 分钟。

 

把n1个步兵和n2个骑兵派成一列,已知连续的步兵不超过k1个,连续的骑兵不超过k2个,求总可能排列情况数

 

定义dp[i][j][2],指使用i个步兵,j个骑兵的排列。0代表排头为步兵,1代表排头为骑兵

#include 
#include
#include
#include
#define INF 0x3f3f3f3f#define MOD 100000000using namespace std;typedef long long LL;int N1, N2, K1, K2;const int maxn = 110;int dp[maxn][maxn][2];int main() { scanf("%d%d%d%d", &N1, &N2, &K1, &K2); for (int i = 0; i <= K1; i++) dp[i][0][0] = 1; for (int i = 0; i <= K2; i++) dp[0][i][1] = 1; for (int i = 1; i <= N1; i++) { for (int j = 1; j <= N2; j++) { for (int k = 1; k <= min(i, K1); k++) { dp[i][j][0] = (dp[i][j][0] + dp[i - k][j][1]) % MOD; } for (int k = 1; k <= min(j, K2); k++) { dp[i][j][1] = (dp[i][j][1] + dp[i][j - k][0]) % MOD; } } } int ans = (dp[N1][N2][0] + dp[N1][N2][1]) % MOD; printf("%d\n", ans); return 0;}

 

转载于:https://www.cnblogs.com/xFANx/p/8436652.html

你可能感兴趣的文章
设置一个临时变量交换两个变量的值
查看>>
java:关于SerialVersionUid
查看>>
nagios与cacti的整合
查看>>
使用RHEL6.3+PXE+DHCP+Apache+NFS+KickStart 无人值守安装RHEL6.3
查看>>
JXL GC 问题探讨
查看>>
并发编程四之互斥
查看>>
极速免费-Magento开源产品上传利器magmi
查看>>
magento如何获得产品的属性Minimum Qty Allowed in Shopping Cart
查看>>
FreeMarker循环变量内建函数
查看>>
Python中time模块详解
查看>>
java 的模板方式设计模式
查看>>
跳转到servlet出现java.lang.InstantiationException:
查看>>
RedHat7 配置VNCServer
查看>>
git 回滚版本
查看>>
Nginx反向代理实现会话(session)保持的两种方式
查看>>
Nginx配置指令location匹配符优先级和安全问题
查看>>
sc create 创建启动服务带参数 目录不能有空格
查看>>
Glusterfs初体验
查看>>
Centos搭建SVN服务器三步曲
查看>>
NC-ERP IUFO系统管理要点
查看>>