博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ1560: [JSOI2009]火星藏宝图
阅读量:4839 次
发布时间:2019-06-11

本文共 1203 字,大约阅读时间需要 4 分钟。

Description

Input

Output

Sample Input

4 10
1 1 20
10 10 10
3 5 60
5 3 30

Sample Output

-4

HINT

 

严格来说这应该已经不算是DP了。。
找到性质就变成一个有理有据的贪心了:因为它只能往右下走,所以它构成的三角形一定是钝角三角形
然后两边平方和是必定小于斜边平方和
又因为水果不能是负数,那就大力贪心
考虑nm做法:只要能A->B->C,就绝对不走B->C
储存每列的最大值,跑一遍即可
代码如下:
//MT_LI#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long#define mp(x,y) make_pair(x,y)#define INF 1e9#define pll pair
#define pii pair
using namespace std;inline ll read(){ ll f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}int stack[20];inline void write(int x){ if(x<0){putchar('-');x=-x;} if(!x){putchar('0');return;} int top=0; while(x)stack[++top]=x%10,x/=10; while(top)putchar(stack[top--]+'0');}inline void pr1(int x){write(x);putchar(' ');}inline void pr2(int x){write(x);putchar('\n');}struct point{ int x,y,d;}a[210000];int f[2100];int pos[2100];bool cmp(point a,point b){ if(a.x!=b.x)return a.x

 

转载于:https://www.cnblogs.com/MT-LI/p/10326736.html

你可能感兴趣的文章
[Mac入门]如何在Mac下显示Finder中的所有文件
查看>>
证明二叉查找树所有节点的平均深度为O(logN)
查看>>
JavaScript基础--简单功能的计算器(十一)
查看>>
WPF Visifire使用 ---- 基础篇二
查看>>
SSAS: Using DMV Queries to get Cube Metadata
查看>>
操作系统存储器管理选择题精练
查看>>
一条咸鱼的养成
查看>>
修复LSP 解决不能上网问题
查看>>
第四周作业总结
查看>>
修改之前某次commit日志和内容
查看>>
动态规划:HDU1712-ACboy needs your help(分组背包问题)
查看>>
PAT A1009 Product of Polynomials(25)
查看>>
libFFM 与 python-libffm 安装遇到的一系列问题-解决方案
查看>>
数据摘要pandas
查看>>
浅谈C语言中的位段
查看>>
2019.04.25 第七次训练 【2017-2018 ACM-ICPC Asia East Continent League Final (ECL-Final 2017)】...
查看>>
javascript正则表达式复习
查看>>
【JVM】类加载器及双亲委派机制实例解析
查看>>
python 生成 pyc 文件
查看>>
linux清除git账号密码
查看>>