题目戳这里：http://www.lydsy.com/JudgeOnline/problem.php?id=1597 2102912 Kamisama123 1597 Accepted 6076 kb 152 ms C++/Edit 1171 B 2017-06-07 19:44:16 2102894 Kamisama123 1597 Accepted 6080 kb 160 ms C++/Edit 982 B 2017-06-07 19:37:12 2102878 Kamisama123 1597 Wrong_Answer 6076 kb 64 ms C++/Edit 1234 B 2017-06-07 19:32:17 2102871 Kamisama123 1597 Accepted 3168 kb 168 ms C++/Edit 867 B 2017-06-07 19:29:20 2102867 Kamisama123 1597 Wrong_Answer 3684 kb 64 ms C++/Edit 1233 B 2017-06-07 19:28:16 2102864 Kamisama123 1597 Wrong_Answer 2512 kb 16 ms C++/Edit 1225 B 2017-06-07 19:26:02 2102828 Kamisama123 1597 Wrong_Answer 25708 kb 16 ms C++/Edit 1032 B 2017-06-07 18:58:25 2102826 Kamisama123 1597 Wrong_Answer 2512 kb 16 ms C++/Edit 1030 B 2017-06-07 18:57:57 真是wa了又a，a了又wa。 搞了半天是最开始初始化弄错了。。。 这是一道简单的入门斜率优化dp题。 首先如果一块土地它的长宽都比另一个土地大，那么小土地是没有什么屁用的。因为你买大土地在带上一个小土地，小土地就相当于免费送了。 所以我们按照土地的长排序，把宽稍微处理一下，就能弄出来一个长是递增，宽是递减的一堆土地。 我们把f[i]定义为买前i个土地最小花费，所以易得dp方程。 我用a[i].x表示第i个土地长，a[i].y表示宽。 f[i]=min{f[j]+a[i].x*a[j+1].y}； 但是n是50000的范围，n^2枚举j肯定爆炸。 所以我们用斜率优化dp思想。 令k
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define N 100005 #define dnt long long using namespace std; struct date{ dnt x,y; }; date a[N],aa[N]; bool comp(const date&a,const date&b){ if(a.x<b.x)return 1; else if(a.x==b.x)if(a.y>b.y)return 1; else return 0; else return 0; } bool vis[N]; dnt n,num,f[N],head,tail,q[N]; int main(){ scanf("%lld",&n); for(dnt i=1;i<=n;i++)scanf("%lld%lld",&a[i].x,&a[i].y); sort(a+1,a+n+1,comp); dnt last=a[n].y;vis[n]=1; for(dnt i=n-1;i>=1;i--){ if(a[i].y>last){ last=a[i].y; vis[i]=1; } } for(dnt i=1;i<=n;i++) if(vis[i]==1){ aa[++num].x=a[i].x; aa[num].y=a[i].y; } for(dnt i=1;i<=num;i++){ while(head<tail&&f[q[head+1]]-f[q[head]]<=aa[i].x*(aa[q[head]+1].y-aa[q[head+1]+1].y)) head++; dnt j=q[head]; f[i]=f[j]+aa[i].x*aa[j+1].y; while(head<tail&&(f[i]-f[q[tail]])*(aa[q[tail]+1].y-aa[q[tail-1]+1].y)>=(f[q[tail]]-f[q[tail-1]])*(aa[i+1].y-aa[q[tail]+1].y)) tail--; q[++tail]=i; } printf("%lld\n",f[num]); return 0; }