不用long long的话只能ac一半的点而且完全查不出来错...放弃cin保平安..
x[i],y[i]分别为第i块土地的长和宽,输入后需要排序然后去掉冗余数据,最后得到的x[i]递增y[i]递减(或者y[i]递增x[i]递减),因为如果x[i]>x[j]的同时y[i]>y[j]则j是不必要存在的,可以把它和i一起买而不花费任何多余的钱
然后就是动规和斜率优化,维护一个下凹折线,从图可以看出是后面的点减前面的点算斜率..
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #include<cmath> 6 using namespace std; 7 int n; 8 struct wtff{ 9 long long x; 10 long long y; 11 }wtf[50010]; 12 long long x[50010]={},y[50010]={}; 13 long long f[50010]={}; 14 long long q[50010]={}; 15 int head=0,tail=0; 16 bool mycmp(wtff a,wtff b){ 17 return (a.x<b.x|| 18 (a.x==b.x&&a.y<b.y)); 19 } 20 inline double www(int a,int b){ 21 return ((double)(f[a]-f[b])/(y[b+1]-y[a+1])); 22 } 23 int main(){ 24 scanf("%d",&n); 25 for(int i=1;i<=n;i++){ 26 scanf("%d%d",&wtf[i].x,&wtf[i].y); 27 } 28 sort(wtf+1,wtf+1+n,mycmp); 29 int en=0; 30 int bign=-100; 31 for(int i=n;i>=1;i--){ 32 if(wtf[i].y>bign){ 33 if(wtf[i].x!=x[en]){ 34 x[++en]=wtf[i].x; 35 y[en]=wtf[i].y; 36 } 37 else{ 38 x[en]=wtf[i].x; 39 y[en]=wtf[i].y; 40 } 41 bign=wtf[i].y; 42 } 43 } 44 for(int i=1;i<=en/2;i++){ 45 swap(x[i],x[en+1-i]); 46 swap(y[i],y[en+1-i]); 47 } 48 for(int i=1;i<=en;i++){ 49 while(head<tail&&www(q[head+1],q[head])<x[i]){ 50 head++; 51 } 52 int j=q[head]; 53 f[i]=f[j]+x[i]*y[j+1]; 54 while(head<tail&&www(i,q[tail])<www(q[tail],q[tail-1])){ 55 tail--; 56 } 57 q[++tail]=i; 58 } 59 cout<<f[en]<<endl; 60 return 0; 61 }