博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
例题9-10 UVa1626&&POJ1141 Brackets Sequence(DP)
阅读量:5879 次
发布时间:2019-06-19

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

题意:

看白书

要点:

状态转移方程真难想,这基本上是个区间DP问题,但还得考虑首尾已经是正规的,这两种情况都要考虑,而且还互相干扰,最后还得打印解,基本就是重新检查一下哪个决策最好。还有个陷阱:输入串可能是空串,所以要用gets。

15546092 Accepted 4024K 32MS 1166B 2016-05-24 14:57:43
#include
#include
#include
#include
using namespace std;char str[1000];int d[1000][1000];int n;bool match(char a, char b){ if ((a == '('&&b == ')')||(a == '['&&b == ']')) return true; return false;}void dp(){ int i, j, k, l; memset(d, 0, sizeof(d)); for (i = 0; i <= n; i++) d[i][i] = 1; //单字符为0 for (l = 2; l <= n; l++) { for (i = 0; i + l <= n; i++) { j = i + l-1; d[i][j] = 0x3f3f3f3f; if (match(str[i],str[j])) d[i][j] = min(d[i][j],d[i + 1][j - 1]); for (k = i; k <= j-1; k++) d[i][j] = min(d[i][j], d[i][k] + d[k+1][j]); } }}void print(int i, int j){ if (i > j) return; if (i == j) { if (str[i] == '(' || str[i] == ')') printf("()"); else printf("[]"); return; } int ans = d[i][j]; if (match(str[i], str[j]) && (ans == d[i + 1][j - 1])) { printf("%c", str[i]); print(i + 1, j - 1); printf("%c", str[j]); return; } for (int k = i; k <= j - 1; k++) { if (ans == d[i][k] + d[k + 1][j]) { print(i, k); print(k + 1, j); return; } }}int main(){ gets_s(str); n = strlen(str); dp(); print(0, n-1); printf("\n"); return 0;}

转载于:https://www.cnblogs.com/seasonal/p/10343734.html

你可能感兴趣的文章
day6 shelve模块
查看>>
好作品地址
查看>>
[翻译]Protocol Buffer 基础: C++
查看>>
runloop与线程的关系
查看>>
[Bzoj2246]迷宫探险(概率+DP)
查看>>
[译] 感受 4px 基线网格带来的便利
查看>>
oracle常用函数
查看>>
MYBATIS
查看>>
详解消息队列的设计与使用
查看>>
iOS 项目优化
查看>>
筛选出sql 查询结果中 不包含某个字符
查看>>
8进制与16进制
查看>>
使用Sqoop从mysql向hdfs或者hive导入数据时出现的一些错误
查看>>
mybatis:Invalid bound statement (not found)
查看>>
电脑中毒的现象
查看>>
django表单操作之django.forms
查看>>
ZipOutputStream出现多层目录问题
查看>>
Android Studio 3.0.1 版本包下载
查看>>
[python] 创建临时文件-tempfile模块
查看>>
真的只是随笔
查看>>