HDU_1176_免费馅饼
2024-08-27 20:52:52
http://acm.hdu.edu.cn/showproblem.php?pid=1176
参考自:http://blog.csdn.net/xcszbdnl/article/details/7876283
可将所有的时间段和馅饼看成是一个矩阵,时间就是行数,掉馅饼的就是列数,则就是数字三角形问题,从最底层找一条路径,使得路径上的和最大。
状态转移方程为:dp[i][j]=max(dp[i+1][j-1],dp[i+1][j],dp[i+1][j-1])+pie[i][j]。pie[i][j]为时间i时在j位置掉的馅饼数目。
则AC代码为:
#include<stdio.h>
#include<string.h.>
#define MAX 100001
int pie[MAX][];
int dp[MAX][];
int n;
int main()
{
int i,j,time,location,maxtime,mid,left,right;
while(scanf("%d",&n)!=EOF&&n){
memset(pie,,sizeof(pie));
memset(dp,,sizeof(dp));
maxtime=;
for(i=;i<n;i++){
scanf("%d%d",&location,&time);
pie[time][location+]++;
if(time>maxtime)
maxtime=time;
}
for(i=;i<=;i++)
dp[maxtime][i]=pie[maxtime][i];
for(i=maxtime-;i>=;i--){
for(j=;j<=;j++){
left=dp[i+][j-]+pie[i][j];
mid=dp[i+][j]+pie[i][j];
right=dp[i+][j+]+pie[i][j];
dp[i][j]=(left>mid)?left:mid;
dp[i][j]=(dp[i][j]>right)?dp[i][j]:right;
}
}
printf("%d\n",dp[][]);
}
return ;
}
最新文章
- 【JavaScript】--重点解析之跨域请求
- mac os 禁止apache httpd自动启动(转)
- java 深入浅出工厂模式
- Android-短信验证
- 以WCF安全认证方式调用通用权限管理系统获取基础信息资料
- OWIN学习
- 《University Calculus》-chaper13-向量场中的积分-线积分
- [Redux] Extracting Presentational Components -- Todo, TodoList
- ZipFile和ZipInputSteam解压zip文件
- Python函数学习——递归
- C++中的基础特性:封装,继承,多态
- ASP.Net Core 中使用Zookeeper搭建分布式环境中的配置中心系列一:使用Zookeeper.Net组件演示基本的操作
- js判断浏览器的类型,动态调整div布局
- spring web应用
- [转] Eclipse安装SVN插件
- ubuntu16 sogou install
- iOS 模态框覆盖导航栏
- ${__BeanShell(${SCRIPT})}
- Codeforces 1131 B. Draw!-暴力 (Codeforces Round #541 (Div. 2))
- POJ_1703 Find them, Catch them 【并查集】
热门文章
- PLU Decomposition
- Cracking the Coding Interview 150题(二)
- nginx-1.5.10 之mips编译到RT5350
- bug统计分析续(一)基于SQL的Bug统计方法
- 自己动手写shell命令之ls -R1fF
- Android 智能问答机器人的实现
- 【bzoj1303】[CQOI2009]中位数图
- win7 32位解决matlab out of memory问题
- 浅谈C++多态性(转载)
- bzoj 2100: [Usaco2010 Dec]Apple Delivery【spfa】