- #pragmacomment(linker, "/STACK:1024000000,1024000000")
- #include
- #include
- #include
- #include
- #include
- #include
- #include<set>
- #include
- #include
- #include
- #include
- using namespace std;
- typedef long long LL;
- const doublepi=acos(-1.0),eps=1e-10;
- void File()
- {
- freopen("D:\\in.txt","r",stdin);
- freopen("D:\\out.txt","w",stdout);
- }
- template <classT>
- inline voidread(T &x)
- {
- charc = getchar();
- x =0;
- while(!isdigit(c)) c = getchar();
- while(isdigit(c))
- {
- x = x *10+ c -'0';
- c = getchar();
- }
- }
- int n,k;
- long longdp[50010][110];
- struct X
- {
- long long w,h;
- }s[50010],tmp[50010];
- intq[50010],f1,f2;
- bool cmp(X a,X b)
- {
- if(a.w!=b.w)returna.w>b.w;
- returna.h>b.h;
- }
- booldelete1(intt,inta,intb,int c)
- {
- if(dp[b][t]+s[b+1].w*s[c].h<=dp[a][t]+s[a+1].w*s[c].h)return 1;
- return 0;
- }
- booldelete2(intt,inta,intb,int c)
- {
- if( (dp[c][t]-dp[b][t])*(s[b+1].w-s[a+1].w)>=
- (dp[b][t]-dp[a][t])*(s[c+1].w-s[b+1].w) )return 1;
- return 0;
- }
- int main()
- {
- while(~scanf("%d%d",&n,&k))
- {
- k=min(n,k);
- for(inti=1;i<=n;i++) scanf("%lld%lld",&tmp[i].w,&tmp[i].h);
- sort(tmp+1,tmp+1+n,cmp);intsz=1;
- s[sz].h=tmp[1].h; s[sz].w=tmp[1].w;
- for(inti=2;i<=n;i++)
- {
- if(tmp[i].h<=s[sz].h)continue;
- sz++; s[sz].h=tmp[i].h; s[sz].w=tmp[i].w;
- }
- for(inti=1;i<=sz;i++) dp[i][1]=s[1].w*s[i].h;
- for(intj=2;j<=k;j++)
- {
- f1=f2=0; q[0] = j-1;
- for(inti=j;i<=sz;i++)
- {
- while(1)
- {
- if(f2-f1+1<2)break;
- if(delete1(j-1,q[f1],q[f1+1],i)) f1++;
- else break;
- }
- dp[i][j]=dp[q[f1]][j-1]+s[q[f1]+1].w*s[i].h;
- while(1)
- {
- if(f2-f1+1<2)break;
- if(delete2(j-1,q[f2-1],q[f2],i)) f2--;
- else break;
- }
- f2++; q[f2]=i;
- }
- }
- long longans=dp[sz][1];
- for(intj=2;j<=k;j++) ans=min(ans,dp[sz][j]);
- printf("%lld\n",ans);
- }
- return 0;
- }
来源: