ACM_成绩单(区间dp套dp)
ฅ'ω'ฅ♪

ACM_成绩单(区间dp套dp)

#2292. 「THUSC 2016」成绩单

这一看就知道是dp阿(自信!

而且还能看出是区间dp哼哼

思路

每次都取子序列,可以设一个(f(i,j))

其值表示删掉区间([i,j])所需的最小代价

好!然后就不会转移了。

其实,每一次取的代价都是相互独立的,

所以对于拥有同样值域的子列,取走的代价的都是一样的

可以设出( dp( l , r , i , j ) )表示从i到j的转移

域是( [l,r]),这个dp组的值就是删掉( [i,j])中若干个数后能使剩下的数都在域内的最小代价;

给出(G(i,j))为删掉此区间所有数的最小代价。

这样我们就可以转移了

(G[l][r]=dp[l][r][i][j]+A+B*(r-l)*(r-l))

( dp[k][l][i][t]=min(dp[k][l][i][t],dp[k][l][i][t]+G[i+1][t]) )

( dp[l][r][i][j]=min(G[i][k]+dp[l][r][k+1][j],dp[l][r][i][j]+dp[l][r][k+1][j]) )

加个离散化

然后余下的到n继续维护就可以了,

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <experimental/string_view>
#define lodou long double
#define lll __int128
#define INmF 0x3f3f3f3f
#define lbt(x) (x&(-x))
#define mes(a,b) memset(a,b,sizeof(a))
#define qwq(a,b) for(int i=a ;i<=b;++i)
#define qeq(a,b) for(int j=a ;j<=b;++j)
#define IOS ios::sync_with_stdio(false)
#define UPCASE( c ) ( ((c) >= 'c' && (c) <= 'z') ? ((c) - 0x20) : (c) )
#define pb push_back
#define mkp make_pair
using namespace std;
using namespace __gnu_pbds;

using pii=pair<int,int>;
using Balanced_Tree=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
Balanced_Tree seq;

const double Eps = 1e-8 ;
const double pi  = acos(-1) ;
const long long mod = 1e9+7 ;
typedef long long int ll;


inline ll pow_mod (ll a,ll b) {ll res=1;a%=mod; if(b<0) return -1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
inline ll fas_mul (ll a,ll b) { return ( (a*b-(ll)(((long double)a*b+0.5)/mod)*mod)%mod+mod)%mod ; }


namespace io {

    #define _ read()
    #define out(a) write(a)
    #define outn(a) out(a),putchar('\n')

    #define I_int __int128
    inline I_int read() {
        I_int x = 0 , f = 1 ; char c = getchar() ;
        while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
        while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
        return x * f ;
    }
    char F[ 200 ] ;
    inline void write( I_int x ) {
        if( x == 0 ) { putchar( '0' ) ; return ; }
        I_int tmp = x > 0 ? x : -x ;
        if( x < 0 ) putchar( '-' ) ;
        int cnt = 0 ;
        while( tmp > 0 ) {
            F[ cnt ++ ] = tmp % 10 + '0' ;
            tmp /= 10 ;
        }
        while( cnt > 0 ) putchar ( F[ -- cnt ] ) ;
    }
    #undef I_int

}using namespace io ;

const int Maxn = 55 ;
int w[Maxn]={0} , por[Maxn] ;
int dp[Maxn][Maxn][Maxn][Maxn] ,
    G[Maxn][Maxn] ;
int main()
{
  int n=_ , A=_ , B=_ ;
  int bz = n*A  , tot=0 ;
  qwq( 1 , n )
  {
      w[i]=_;
      por[++tot]=w[i] ;
  }
  sort( por+1 , por+tot+1 ) ;
  tot = unique( por+1 , por+tot+1 )-por-1 ;
  qwq( 1 , n )
    w[i] = lower_bound( por+1 , por+tot+1 , w[i] ) -por ;

  mes( dp , INmF ) ;
  mes( G , INmF ) ;
  qwq( 1 , n )
    dp[i][i][w[i]][w[i]]=0 ,
    G[i][i-1] = 0 ;


  for( int l=n ; l>=1 ; --l )
    for( int r=l ; r<=n ; ++r )
    {
      qwq( 1 , tot )
        qeq( 1 , tot )
        {
          if( dp[l][r][i][j]>=bz )
            continue ;
          G[l][r] = min( dp[l][r][i][j]+A+B*(por[j]-por[i])*(por[j]-por[i]),G[l][r] );
          for( int k=r+1 ; k<=n ; ++k )
            dp[l][k][ min(i,w[k]) ][ max(j,w[k]) ] = min( dp[l][k][ min(i,w[k]) ][ max(j,w[k]) ] ,dp[l][r][i][j]+G[r+1][k-1] );
        }
        for( int k=r+1 ; k<=n ; ++k )//余列需要维护
            G[l][k] = min( G[l][k] , G[l][r]+G[r+1][k] );
    }
    outn( G[1][n] ) ;
}
CANCEL

-评论-

Here you can post what you want to say, if you have more information please contact me by the following way.

-昵称-
-QQ-
-邮箱-
想说些什么?
-SUBMIT-

-电联 Phone-

+86 18520664652

-邮箱 Email-

boogieLing_o@163.com

boogieLing_o@qq.com

Your name. OS platform Browser model

What do you want to say?

created time

游說萬乘苦不早,著鞭跨馬涉遠道。

阿凌的貓爬架

幸會,

激活Ubuntu

转到“设置”以激活Ubuntu。

R0's board.