LPS HDOJ 4745 Two Rabbits
2024-08-30 10:14:13
/*
题意:一只兔子顺时针跳,另一只逆时针跳,跳石头权值相等而且不能越过起点
LPS:这道就是LPS的应用,把环倍增成链,套一下LPS,然而并不能理解dp[i][i+n-2] + 1,看别人的解题报告吧,以后来补(玩游戏)
详细解释 */
/************************************************
* Author :Running_Time
* Created Time :2015-8-8 16:57:23
* File Name :HDOJ_4747_LPS.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int MAXN = 2e3 + ;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + ;
int a[MAXN], dp[MAXN][MAXN]; int main(void) { //HDOJ 4745 Two Rabbits
int n;
while (scanf ("%d", &n) == ) {
if (!n) break;
for (int i=; i<=n; ++i) {
scanf ("%d", &a[i]);
a[i+n] = a[i];
}
memset (dp, , sizeof (dp));
for (int i=; i<=*n; ++i) dp[i][i] = ;
for (int i=; i<*n; ++i) {
for (int j=; j+i-<=*n; ++j) {
if (a[j] == a[j+i-]) dp[j][j+i-] = dp[j+][j+i-] + ;
else {
dp[j][j+i-] = max (dp[j+][j+i-], dp[j][j+i-]);
}
}
}
int ans = ;
for (int i=; i<=n; ++i) {
ans = max (ans, dp[i][i+n-]);
ans = max (ans, dp[i][i+n-] + );
}
printf ("%d\n", ans);
} return ;
}
最新文章
- node(ActiveMq)
- iOS开发之使用XMPPFramework实现即时通信(一)
- [专业名词&#183;硬件] 2、DC\DC、LDO电源稳压基本常识(包含基本原理、高效率模块设计、常见问题、基于nRF51822电源管理模块分析等)&#183;长文
- rem在响应式布局中的应用
- VIM辅导:视频教程,文档资料,经典插件
- Git.Framework 框架随手记--ORM项目工程
- EL 标准格式时间 转换成 常用时间yyyy-MM-dd
- dfs.datanode.max.xcievers参数导致hbase集群报错
- linux安装
- C++ sizeof操作符的用法和strlen函数的区别
- 淘宝的ip地址库
- activity的测试工程activiti-explorer使用
- smartassembly 使用指南
- synchronized 关键字
- Redis技术分享
- NHibernte教程(10)--关联查询
- x64类型的程序逆向思考
- homestead安装
- jenkins使用git拉取gitlab代码
- Jmeter如何把响应数据的结果保存到本地的一个文件
热门文章
- Our Journey of Dalian Ends 乌鲁木齐网络赛 最小费用最大流
- [bzoj3910]火车_并查集_倍增LCA
- Java中如何获取spring中配置的properties文件内容
- mysql建表语句key的含义
- 在Windows下搭建RocketMQ
- 条款三:尽量用new和delete而不用malloc和free
- 【CV论文阅读】Image Captioning 总结
- Linux学习系列之Inotify+Rsync实现实时数据同步
- struts1与struts2的差别
- 合并小图片利器TexturePacker GUI