【CodeForces】【321E】Ciel and Gondolas

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

DP优化/四边形不等式

这题……跟邮局那题简直一模一样吧……好水的E题……

设dp[i][j]表示前 i 艘“gondola”坐了前 j 个人，那么方程即为$dp(i,j)=min\{ dp[i-1][k]+w[k][j] \} (i\leq k\leq j)$

很明显$w(l,r)=\sum_{i=l}^r \sum_{j=l}^r u(i,j) /2$是满足四边形不等式的……那么根据决策单调性直接搞就行了……

 //CF 321E

 #include<vector>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 using namespace std;

 //#define debug

 int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}

     return v*sign;

 }

 typedef long long LL;

 const int N=,INF=~0u>>;

 /*******************tamplate********************/

 LL u[][],n,m,w[][],dp[][];

 int s[][];

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("input.txt","r",stdin);

 //    freopen("output.txt","w",stdout);

 #endif

     n=getint(); m=getint();

     F(i,,n) F(j,,n) u[i][j]=getint();

     F(i,,n) F(j,,n) u[i][j]+=u[i-][j]+u[i][j-]-u[i-][j-];

     F(i,,n) F(j,i+,n) w[i][j]=u[j][j]-u[i-][j]-u[j][i-]+u[i-][i-];

     #ifdef debug

     F(i,,n) {F(j,,n) printf("%3d",w[i][j]);puts("");}

     #endif

     F(i,,m) F(j,,n) dp[i][j]=INF;

     F(i,,n){

         dp[][i]=w[][i];

         s[][i]=;

     }

     F(i,,m){

         s[i][n+]=n;

         D(j,n,i)

             F(k,s[i-][j],s[i][j+])

                 if (dp[i-][k]+w[k+][j]<dp[i][j]){

                     s[i][j]=k;

                     dp[i][j]=dp[i-][k]+w[k+][j];

                 }

     }

     printf("%I64d\n",dp[m][n]/);

     return ;

 }