HDU 1244 【DP】
2024-08-24 14:44:30
题意:
中文。
思路:
先初步处理,用give-take求出每个城市剩的钱。
求解问题转化成使得和不小于0的最长连续字串。
枚举起点,然后当该起点加的和为负时开始枚举下一起点。(这个状态的转移)
2WA原因:
因为扩展了2倍的点使得求解的最长连续的点有可能大于n。
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int tmp[];
int main()
{
int n,give,take;
while(scanf("%d",&n)!=EOF)
{
int maxn=;
tmp[]=;
for(int i=;i<=n;i++)
{
scanf("%d",&give);
scanf("%d",&take);
tmp[i]=give-take;
}
for(int i=n+;i<=*n;i++)
{
tmp[i]=tmp[i-n];
}
int j=;
int num=;
for(int i=;i<=n;i++)
{
num-=tmp[i-];
for(;j<=*n;j++)
{
if(num<)
break;
num+=tmp[j];
if(num>=)
maxn=max(j-i+,maxn);
}
if(maxn>=n)
break;
}
maxn=min(n,maxn);
printf("%d\n",maxn);
}
}
最新文章
- CSS性能分析,如何优化CSS提高性能
- 面向对象tab栏例子分析
- WORD2007多级列表
- linux -小记(2)问题:yum 安装报错";Another app is currently holding the yum lock; waiting for it to exit... ...: yum Memory : 26 M RSS (868 MB VSZ) Started: Wed Oct 26 22:48:24 2016 - 0";
- Java的从浅至深绕坑而行的学习
- POJ 1236 Network of Schools (Tarjan + 缩点)
- 《Java程序书面采访猿收藏》之 instanceof的作用是什么
- 移动端ios 输入框fixed固定在底部 焦点时乱跳加遮盖问题的解决 转自zhangyunling 加个人项目解决方案
- Hadoop集群环境安装
- Codeforces 279D The Minimum Number of Variables 状压dp
- 金融量化分析【day112】:因子选股
- LeetCode: 106_Construct Binary Tree from Inorder and Postorder Traversal | 根据中序和后序遍历构建二叉树 | Medium
- Hadoop技术里面有BSP模型、MPI模型
- Kaggle Titanic补充篇
- vue组件库(四):组件功能模块划分
- 轻量级Java持久化框架,Hibernate完美助手,Minidao 1.6.2版本发布
- JavaScript的 onclick 事件是如何调用jquery 方法的
- CSS艺术字
- linux 的服务与进程管理(二)
- MySQL知识小结
热门文章
- .net4.5注册到iis
- CSS3实现单行、多行文本溢出(省略号的形式出现)
- loadrunner11报错:Error -27780
- UVALive 2238 Fixed Partition Memory Management 固定分区内存管理(KM算法,变形)
- 7-Java-C(四平方和)
- Bug的分类和管理流程
- k8s 重要概念[转]
- resnet.caffemodel
- Linux下scp报Permission denied错误的解决方法
- shell $() vs ${}