SPOJ-SQRBR Square Brackets
2024-10-18 18:26:00
原题传送：http://www.spoj.pl/problems/SQRBR
动态规划。
设f[i][j]表示前i个位置在合法情况下缺少j个右括号的方案数。
转移方程为：
f[i][j] = f[i-1][j-1] (第i个地方必须为'[')
f[i][j] = f[i-1][j-1] + f[i-1][j+1] (分第i个位置放左括号和右括号的情况)
写的第一份代码不是很严谨，j-1变为负值，但spoj判ac了。
#include <stdio.h>
#include <string.h>
#define N 205 int f[N][N], n, k;
bool h[N]; int main()
{
int t, d;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &k);
memset(h, , sizeof h);
memset(f, , sizeof f);
f[][] = ;
for(int i = ; i <= k; i++)
{
scanf("%d", &d);
h[d] = ;
}
for(int i = ; i <= * n; i++)
{
for(int j = ; j <= * n; j++)
{
if(h[i])
{
f[i][j] = f[i-][j-];
}
else
{
f[i][j] = f[i-][j-] + f[i-][j+];
}
}
}
printf("%d\n", f[*n][]);
}
return ;
}
修改后为：
#include <stdio.h>
#include <string.h>
#define N 205 int f[N][N], n, k;
bool h[N]; int main()
{
int t, d;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &k);
memset(h, , sizeof h);
memset(f, , sizeof f);
f[][] = ;
for(int i = ; i <= k; i++)
{
scanf("%d", &d);
h[d] = ;
}
for(int i = ; i <= * n; i++)
{
for(int j = ; j <= * n; j++)
{
if(h[i])
{
if(j != )
f[i][j] = f[i-][j-];
else
f[i][j] = ;
}
else
{
if(j != )
f[i][j] = f[i-][j-] + f[i-][j+];
else
f[i][j] = f[i-][j+];
}
}
}
printf("%d\n", f[*n][]);
}
return ;
}
最新文章
- angularJS——自定义服务provider之$get
- MFC程序中使用调试宏ASSERT()、ASSERT_VALID()、VERIFY()和TRACE()的区别
- [java基础]循环结构2
- win下隐藏任务栏
- ASP.NET MVC 实现二级域名
- VS 2005部署应用程序提示“应用程序无法正常启动( 0x0150002)” 解决方案
- 2014年6月5日 深圳 IBM 安全解决方案会议通知
- 狗狗40题~（Volume B）
- 跨域访问 REST API
- php结合redis实现高并发下的抢购、秒杀功能 (转载)
- 第03章-VTK系统概述（1）
- 前端工程化系列[03]-Grunt构建工具的运转机制
- js 回车键事件
- lnmp源码编译安装zabbix
- 一口一口吃掉Hexo（四）
- Remove Duplicates from Sorted Array II leetcode java
- hashcode 知识点
- @Secured()、 @PreAuthorize() 、 @RolesAllowed()
- ajax做显示信息以后用ajax、Bootstrp做弹窗显示信息详情
- Codeforces Round #301 (Div. 2) D. Bad Luck Island 概率DP