UVaLive 6801 Sequence (计数DP)

时间:2022-11-01 20:13:04

题意:给定一个序列,有 n 个数,只有01,然后你进行k次操作,把所有的1变成0,求有多种方法。

析:DP是很明显的,dp[i][j] 表示进行第 i 次操作,剩下 j 个1,然后操作就两种,把1变成0,把0变成1。也可以用记忆化来做。

代码如下:

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <sstream>
#define frer freopen("in.txt", "r", stdin)
#define frew freopen("out.txt", "w", stdout)
using namespace std; typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 1e3 + 5;
const int mod = 1e9 + 7;
const char *mark = "+-*";
const int dr[] = {1, 0, -1, 0};
const int dc[] = {0, 1, 0, -1};
const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline int Min(int a, int b){ return a < b ? a : b; }
inline int Max(int a, int b){ return a > b ? a : b; }
inline LL Min(LL a, LL b){ return a < b ? a : b; }
inline LL Max(LL a, LL b){ return a > b ? a : b; }
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
}
LL dp[maxn][maxn]; int main(){
int T; cin >> T;
for(int kase = 1; kase <= T; ++kase){
scanf("%d %d", &n, &m);
memset(dp, 0, sizeof dp);
int x, cnt = 0;
for(int i = 0; i < n; ++i){
scanf("%d", &x);
cnt += x;
}
dp[0][cnt] = 1;
for(int i = 1; i <= m; ++i){
for(int j = 0; j <= n; ++j){
if(j > 0) dp[i][j] = (dp[i][j] + dp[i-1][j-1] * (n-j+1)) % mod;
if(j < n) dp[i][j] = (dp[i][j] + dp[i-1][j+1] * (j+1)) % mod;
}
}
printf("Case #%d: %lld\n", kase, dp[m][0]);
}
return 0;
}

  

记忆化搜索:

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <sstream>
#define frer freopen("in.txt", "r", stdin)
#define frew freopen("out.txt", "w", stdout)
using namespace std; typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 1e3 + 5;
const int mod = 1e9 + 7;
const char *mark = "+-*";
const int dr[] = {1, 0, -1, 0};
const int dc[] = {0, 1, 0, -1};
const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline int Min(int a, int b){ return a < b ? a : b; }
inline int Max(int a, int b){ return a > b ? a : b; }
inline LL Min(LL a, LL b){ return a < b ? a : b; }
inline LL Max(LL a, LL b){ return a > b ? a : b; }
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
}
LL dp[maxn][maxn]; LL dfs(int k, int cnt){
if(k == 0) return cnt == 0;
LL &ans = dp[k][cnt];
if(ans >= 0) return ans;
int cnt0 = n - cnt;
ans = 0;
if(cnt > 0) ans = (ans + dfs(k-1, cnt-1) * cnt) % mod;
if(cnt0 > 0) ans = (ans + dfs(k-1, cnt+1) * cnt0) % mod;
return ans;
} int main(){
int T; cin >> T;
for(int kase = 1; kase <= T; ++kase){
scanf("%d %d", &n, &m);
memset(dp, -1, sizeof dp);
int x, cnt = 0;
for(int i = 0; i < n; ++i){
scanf("%d", &x);
cnt += x;
}
printf("Case #%d: %lld\n", kase, dfs(m, cnt));
}
return 0;
}

  

UVaLive 6801 Sequence (计数DP)的更多相关文章

  1. CodeForces 176B Word Cut (计数DP)

    Word Cut Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u Submit St ...

  2. HDU5800 To My Girlfriend 背包计数dp

    分析:首先定义状态dp[i][j][s1][s2]代表前i个物品中,选若干个物品,总价值为j 其中s1个物品时必选,s2物品必不选的方案数 那么转移的时候可以考虑,第i个物品是可选可可不选的 dp[i ...

  3. &lbrack;DP之计数DP&rsqb;

    其实说实在 我在写这篇博客的时候 才刚刚草了一道这样类型的题 之前几乎没有接触过 接触过也是平时比赛的 没有系统的做过 可以说0基础 我所理解的计数dp就是想办法去达到它要的目的 而且一定要非常劲非常 ...

  4. HDU4815&sol;计数DP

    题目链接[http://acm.hdu.edu.cn/showproblem.php?pid=4815] 简单说一下题意: 有n道题,每到题答对得分为a[ i ],假如A不输给B的最小概率是P,那么A ...

  5. HDU 6377 度度熊看球赛 &lpar;计数DP&rpar;

    度度熊看球赛 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Subm ...

  6. 计数dp

    计数dp 计数类的$dp$没做过几个,所以之前都放到"思维"标签下了,后来发现原来这属于一类问题啊...搬过来了. 管道取珠:https://www.lydsy.com/Judge ...

  7. &lbrack;SDOI2010&rsqb;地精部落&lbrack;计数dp&rsqb;

    题意 求有多少长度为 \(n\) 的排列满足 \(a_1< a_2> a_3 < a_4 \cdots\) 或者 $a_1> a_2 < a_3 > a_4\cdo ...

  8. 【BZOJ】2111&colon; &lbrack;ZJOI2010&rsqb;Perm 排列计数 计数DP&plus;排列组合&plus;lucas

    [题目]BZOJ 2111 [题意]求有多少1~n的排列,满足\(A_i>A_{\frac{i}{2}}\),输出对p取模的结果.\(n \leq 10^6,p \leq 10^9\),p是素数 ...

  9. 【AtCoder】AGC022 F - Leftmost Ball 计数DP

    [题目]F - Leftmost Ball [题意]给定n种颜色的球各k个,每次以任意顺序排列所有球并将每种颜色最左端的球染成颜色0,求有多少种不同的颜色排列.n,k<=2000. [算法]计数 ...

随机推荐

  1. php多进程总结

    本文部分来自网络参考,部分自己总结,由于一直保存在笔记中,并没有记录参考文章地址,如有侵权请通知删除.最近快被业务整疯了,这个等抽时间还需要好好的整理一番.   多进程--fork 场景:日常任务中, ...

  2. mongoDB入门必读

    一.概述 MongoDB是一个基于分布式文件存储的数据库开源项目. 由C++语言编写,旨在为WEB应用提供可护展的高性能数据存储解决方案. MongoDB是一个介于关系数据库和非关系数据库之间的产品. ...

  3. uva 1146 Now or late (暴力2-SAT)

    /* 裸地2-SAT问题 关键是模型转化 最小的最大 显然二分 关键是Judge的时候怎么判断 每个航班是早是晚直接影响判断 早晚只能选一个 如果我们定义bool变量xi表示 i航班是否早到 每个航班 ...

  4. centos下httpd-2&period;4的编译安装

    httpd-2.4编译安装     依赖于更高版本的apr和apr-util      apr 全称  apache portable runtime 首先停用低版本的httpd服务 service ...

  5. orm的理解

    orm:是对象->关系->映射,的简称. mvc或者mvc框架中包括一个重要的部分,就是orm,它实现了数据模型于数据库的解耦,即数据模型的设计不需要依赖于特定的数据库,通过简单的配置就可 ...

  6. 背水一战 Windows 10 &lpar;55&rpar; - 控件(集合类)&colon; SemanticZoom&comma; ISemanticZoomInformation

    [源码下载] 背水一战 Windows 10 (55) - 控件(集合类): SemanticZoom, ISemanticZoomInformation 作者:webabcd 介绍背水一战 Wind ...

  7. ASP入门(十三)-Server对象

    Server 对象用于处理服务器上的一些特殊任务,例如,创建组件实例.获取文件路径.执行ASP脚本文件等. Server 对象是体现 ASP 强大功能的一个对象,之前介绍的对象都是针对获取.请求以及简 ...

  8. redis 远程 访问 安全配置

    朋友总结很好,就转载了-> 站长博客 假设两台redis服务器,ip分别为:192.168.1.101和192.168.1.103,如果在101上通过redis-cli访问103上的redis呢 ...

  9. async await的使用

    var sleep = function (time) { return new Promise(function (resolve, reject) { setTimeout(function () ...

  10. html基础概念

    一.HyperText Markup Language   内容,html是弱代码语言,代码编写不严谨 1.超链接  <a href="#">超级链接(anchor)& ...