题意:
中文题意不解释……
思路:
先把x,T存到矩阵里 然后像数塔一样从最底层走一边就行了
dp[i][j]代表在时间为j时 第i个位置最多能吃到多少个馅饼
最后输出第0时刻的5位置的馅饼数量就好了
/* ***********************************************
Author :Sun Yuefeng
Created Time :2016/11/8 18:56:49
File Name :dp.cpp
************************************************ */ #include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<bitset>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<queue>
#include<list>
#define M(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=2e5+;
const int mod=1e7+;
int dx[]= {,,,-,,-,,-};
int dy[]= {,-,,,-,,,-}; int dp[][maxn]; int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n;
while(~scanf("%d",&n)&&n)
{
M(dp,); //初始化矩阵
int maxtime=-,x,T;
for(int i=;i<n;i++)
{
scanf("%d%d",&x,&T);
if(T>maxtime) maxtime=T; //记录最长时间
dp[x][T]++; //T时刻x位置的馅饼+1
}
for(int i=maxtime;i>=;i--)
{
dp[][i-]+=max(dp[][i],dp[][i]); //边界特殊处理
dp[][i-]+=max(dp[][i],dp[][i]);
for(int j=;j<=;j++)
{ //动态方程
dp[j][i-]+=max(dp[j-][i],max(dp[j][i],dp[j+][i]));
}
}
printf("%d\n",dp[][]);
}
return ;
}
[ An Ac a Day ^_^ ] [kuangbin带你飞]专题十二 HDU 1176 免费馅饼的更多相关文章
-
[kuangbin带你飞]专题十二 基础DP1
ID Origin Title 167 / 465 Problem A HDU 1024 Max Sum Plus Plus 234 / 372 Problem B HDU 1 ...
-
[kuangbin带你飞]专题十 匹配问题
A-L 二分匹配 M-O 二分图多重匹配 P-Q 二分图最大权匹配 R-S 一般图匹配带花树 模板请自己找 ID Origin Title 61 / 72 Problem A HD ...
-
[kuangbin带你飞]专题十 匹配问题 一般图匹配
过去做的都是二分图匹配 即 同一个集合里的点 互相不联通 但是如果延伸到一般图上去 求一个一般图的最大匹配 就要用带花树来解决 带花树模板 用来处理一个无向图上的最大匹配 看了一会还是不懂 抄了一遍 ...
-
[kuangbin带你飞]专题十五 数位DP
ID Origin Title 62 / 175 Problem A CodeForces 55D Beautiful numbers 30 / 84 Problem B HD ...
-
[kuangbin带你飞]专题十 匹配问题 二分匹配部分
刚回到家 开了二分匹配专题 手握xyl模板 奋力写写写 终于写完了一群模板题 A hdu1045 对这个图进行 行列的重写 给每个位置赋予新的行列 使不能相互打到的位置 拥有不同的行与列 然后左行右列 ...
-
[kuangbin带你飞]专题十四 数论基础
ID Origin Title 111 / 423 Problem A LightOJ 1370 Bi-shoe and Phi-shoe 21 / 74 Problem B ...
-
[kuangbin带你飞]专题十 匹配问题 二分图多重匹配
二分图的多重匹配问题不同于普通的最大匹配中的"每个点只能有最多一条边" 而是"每个点连接的边数不超过自己的限定数量" 最大匹配所解决的问题一般是"每个 ...
-
[kuangbin带你飞]专题十 匹配问题 二分图最大权匹配
二分图最大权匹配有km算法和网络流算法 km算法模板默认解决最大权匹配的问题 而使用最小费用最大流 是解决最小权匹配问题 这两种办法都可以求最大最小权 需要两次取反 TAT 感觉讲km会很难的样子.. ...
-
[kuangbin带你飞]专题十六 KMP &; 扩展KMP &; Manacher 题解报告
来刷kuangbin字符串了,字符串处理在ACM中是很重要的,一般比赛都会都1——2道有关字符串处理的题目,而且不会很难的那种,大多数时候都是用到一些KMP的性质或者找规律. 点击标题可跳转至VJ比赛 ...
随机推荐
-
R语言-实用数据对象处理函数
length(object) 显示对象中元素/成分的数量 dim(object) 显示某个对象的维度 str(object) 显示某个对象的结构 class(object) 显示某个对象的类或类型 m ...
-
Kafka 分布式消息队列介绍
Kafka 分布式消息队列 类似产品有JBoss.MQ 一.由Linkedln 开源,使用scala开发,有如下几个特点: (1)高吞吐 (2)分布式 (3)支持多语言客户端 (C++.Java) 二 ...
-
查看Flink的Job Graph时的问题
Flink运行Job时,可以通过Job Graph看到执行计划,但是如果用IE,会被坑: 换成谷歌Chrome,就OK了: 这个Job Grap,好像是SVG的,可能是IE不支持SVG,需要安装插件才 ...
-
织梦dedecmsV5.7联动类型无法显示的处理方法
最近织梦dedecms在新的功能中添加了一个联动类型这样的一个功能.所谓的联动类型,类似于一级目录下有二级目录,二级目录下又有三级目录,可以理解为数据结构中树形结构.级和级之间都是有着联系的.为了让大 ...
-
简述SharePoint designer 工作流实现用户撤回申请得解决方案,how to revoke/recall application in SharePoint designer workflow
在工作中很容易碰到用户提出,需要可以撤回申请得需求.有这么几种实现方法. 方案一:designer中加一个parallel(平行)得anction, 然后在里面添加两个平行运行得审批 第一个是给真正得 ...
-
登录MES系统后台服务的操作
一:使用GIt Bash Here打开服务 文件名:MES-Server-API-SC 输入:yarn server//打开服务 文件名:MES-server-API 输入:yarn local//本 ...
-
初入webform的杂七杂八
客户端---IIS(Internet Information Services的缩写,意为互联网信息服务管理器)---.NET framework---数据库 1.Repeater控件:对应的集合有5 ...
-
极路由hosts
cat /etc/hosts 127.0.0.1 localhost tw-vars hiwifi 192.168.199.1 t.w tw t 4006024680.com www.40060246 ...
-
在服务器上搭建wordpress个人博客 php7.2+nginx+mysql+wordperss
买了台VPS,准备搭建一个博客.用过几个博客框架还是觉得Wordpress好用.主题多,插件也非常的便利,而且大多还免费开源.搭建也很简单,其实安装好php+mysql+nginx+wordpress ...
-
VUE设置浏览器icon图标
一.将[logo.png]格式图片转换为[logo.bmp]格式 ps打开图片- 存储为 BMP格式 保存好的[logo.bmp] 格式的图片重命名为[logo.ico] 二.将[logo.ico]图 ...