Lightoj 1025 - The Specials Menu (区间DP)
2024-09-05 14:20:29
题目链接:
Lightoj 1025 - The Specials Menu
题目描述:
给出一个字符串,可以任意删除位置的字符,也可以删除任意多个。问能组成多少个回文串?
解题思路:
自从开始学dp,感觉自己智商一直处于离线状态。席八啊啊啊啊啊啊!今天随机到这个题目,看了好久竟然没有看出来是区间DP。知道是区间DP后立马感觉明白。
情景设定 dp[l][r] 表示 区间 [l, r] 内的回文串数目。
状态转移:dp[l][r] = dp[l][r-1] + dp[l+1][r], 但是这样会加重复的,所以要减去dp[l+1][r-1], 当a[l] == a[r]的时候,对于区间[l, r]之间的回文串,就可以变成以a[l]与a[r]结尾的,然后就需要加上。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std;
typedef long long LL;
const int maxn = ;
const int INF = 0x3f3f3f3f;
LL dp[maxn][maxn];
char a[maxn]; int main ()
{
int T;
scanf ("%d", &T);
for (int t=; t<=T; t++)
{
scanf ("%s", a+);
int len = strlen (a+);
memset (dp, , sizeof(dp)); for (int i=; i<=len; i++)
for (int l=; l+i-<=len; l++)
{
int r = l + i - ;
dp[l][r] += dp[l+][r];
dp[l][r] += dp[l][r-]; if (a[l] == a[r]) dp[l][r] += ;
else dp[l][r] -= dp[l+][r-]; }
printf ("Case %d: %lld\n", t, dp[][len]);
}
return ;
}
最新文章
- spring四种依赖注入方式
- knockout.js 简介
- ZAM 3D 制作3D动画字幕 用于Xaml导出
- C# 为私有方法添加单元测试(反射)
- iOS Node Conflict svn冲突
- FZU 2214 Knapsack problem(背包问题)
- jQuery停止动画和判断是否处于动画状态
- HTML+CSS学习总结:
- How to use Mac Terminal
- nvl()函数
- JqueryUI 为什么TypeError: $(...).slides is not a function
- 20个 Unix/Linux 命令技巧
- 关于Core Data的一些整理(五)
- About Spring
- JavaScript(8)——JSON
- 200行自定义异步非阻塞Web框架
- cookie和session有什么区别,请你谈谈cookie的缺点
- vhost:一种 virtio 高性能的后端驱动实现
- SQL练习题题目
- SVM理解
热门文章
- mysqld与mysqld_safe的区别
- openssl 再爆惊天漏洞及紧急修复指南
- eclipse配置android
- 浅谈JavaScript的Canvas(绘制图形)
- 读写ini配置文件 .
- 20170223 遇到自建表里面相同key值数据不唯一
- linux网络配置及IP绑定
- [RK3288][Android6.0] 调试笔记 --- 系统识别不同硬件版本方法【转】
- android adb 源码框架分析(1 系统)【转】
- iOS多线程全套:线程生命周期,多线程的四种解决方案,线程安全问题,GCD的使用,NSOperation的使用