本文共 1203 字，大约阅读时间需要 4 分钟。
严格来说这应该已经不算是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
