「THUSC 2016」成绩单 & 方块消除（区间dp）

$f[l][r][mi][mx]$表示从l到r发到还没发的部分的最小值为mi最大值为mx时的最小代价。

$f[l][r][0][0]$表示从l到r全部发完的代价。

自己写的无脑dp,枚举中转点k，分成(i,k) (k+1,j)两个区间，分别用mi,mx都在左区间，都在右区间，一个左一个右来转移，这样会发现可以转移过来的都是某个一维或者二维前缀和的形式，于是我开了四个二维数组，暴力维护了6个前缀和更新答案。。。

然后代码就比较鬼畜

 1 //Achen
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<vector>
 7 #include<cstdio>
 8 #include<queue>
 9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 const int N=52;
16 typedef long long LL;
17 typedef double db;
18 using namespace std;
19 int n,sz,w[N],ls[N];
20 LL a,b,f[N][N][N][N];
21 
22 template<typename T>void read(T &x)  {
23     char ch=getchar(); x=0; T f=1;
24     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
25     if(ch=='-') f=-1,ch=getchar();
26     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
27 }
28 
29 LL pf(LL x) { return x*x; }
30 void pre() {
31     sort(ls+1,ls+n+1); 
32     sz=unique(ls+1,ls+n+1)-(ls+1);
33     For(i,1,n) w[i]=lower_bound(ls+1,ls+sz+1,w[i])-ls;
34     memset(f,127/3,sizeof(f));
35     For(i,1,n) {
36         int mi=w[i],mx=w[i];
37         For(j,i,n) {
38             mi=min(mi,w[j]);
39             mx=max(mx,w[j]);
40             f[i][j][mi][mx]=0;
41             f[i][j][0][0]=a+b*pf(ls[mx]-ls[mi]);
42         }
43     }
44 }
45 
46 LL p1[N][N],p2[N][N],p3[N][N],p4[N][N],p5,p6; 
47 void clear() {
48     memset(p1,127/3,sizeof(p1));
49     memset(p2,127/3,sizeof(p2));
50     memset(p3,127/3,sizeof(p3));
51     memset(p4,127/3,sizeof(p4));
52 }
53 
54 void get_min(LL &x,LL y) { if(y<x) x=y; }
55 
56 void solve() {
57     For(len,2,n) For(i,1,n-len+1) {
58         int j=i+len-1;
59         For(k,i,j-1) {
60             clear();
61             Rep(mi,sz,1) {
62                 p5=p6=1e18;
63                 For(mx,mi,sz) {
64                     p5=min(p5,f[i][k][mi][mx]);
65                     p2[mi][mx]=min(p2[mi][mx],p5);
66                     p6=min(p6,f[k+1][j][mi][mx]);
67                     p1[mi][mx]=min(p1[mi+1][mx],p6);
68                     p3[mi][mx]=min(p3[mi+1][mx],f[k+1][j][mi][mx]);
69                     p4[mi][mx]=min(p4[mi+1][mx],f[i][k][mi][mx]);
70                     
71                     get_min(f[i][j][mi][mx],f[i][k][mi][mx]+f[k+1][j][0][0]);
72                     get_min(f[i][j][mi][mx],f[i][k][0][0]+f[k+1][j][mi][mx]);
73                     
74                     get_min(f[i][j][mi][mx],f[i][k][mi][mx]+p1[mi][mx]);
75                     get_min(f[i][j][mi][mx],p2[mi][mx]+f[k+1][j][mi][mx]);
76                     get_min(f[i][j][mi][mx],p5+p3[mi][mx]);
77                     get_min(f[i][j][mi][mx],p4[mi][mx]+p6);
78                     get_min(f[i][j][0][0],f[i][j][mi][mx]+a+b*pf(ls[mx]-ls[mi]));
79                 }
80             }  
81             get_min(f[i][j][0][0],f[i][k][0][0]+f[k+1][j][0][0]);
82         }
83     }
84     printf("%lld
",f[1][n][0][0]);
85 }
86 
87 int main() {
88 #ifdef ANS
89     freopen(".in","r",stdin);
90     freopen(".out","w",stdout);
91 #endif
92     read(n);
93     read(a); read(b);
94     For(i,1,n) read(w[i]),ls[i]=w[i];
95     pre();
96     solve();
97     Formylove;
98 }

View Code

正解的转移非常简单，写出这种转移的人大概和我这种zz之间有着几个世纪的代沟。。。

一开始我的代码wa了才找了个正解来抄，结果还是wa了，最后发现是离散写错了。。。lower_bound里面sz写成了n。。

这里$f[l][r][mi][mx]$应该是从l到r，r一定还没发的最小代价，具体还是看代码吧，感性理解一下

 1 //Achen
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<vector>
 7 #include<cstdio>
 8 #include<queue>
 9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 const int N=52;
16 typedef long long LL;
17 typedef double db;
18 using namespace std;
19 int n,sz,w[N],ls[N];
20 LL a,b,f[N][N][N][N];
21 
22 template<typename T>void read(T &x)  {
23     char ch=getchar(); x=0; T f=1;
24     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
25     if(ch=='-') f=-1,ch=getchar();
26     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
27 }
28 
29 LL pf(LL x) { return x*x; }
30 void pre() {
31     sort(ls+1,ls+n+1); 
32     sz=unique(ls+1,ls+n+1)-(ls+1);
33     For(i,1,n) w[i]=lower_bound(ls+1,ls+sz+1,w[i])-ls;
34     memset(f,127/3,sizeof(f));
35     For(i,1,n) {
36         int mi=w[i],mx=w[i];
37         For(j,i,n) {
38             mi=min(mi,w[j]);
39             mx=max(mx,w[j]);
40             f[i][j][mi][mx]=0;
41             f[i][j][0][0]=a+b*pf(ls[mx]-ls[mi]);
42         }
43     }
44 }
45 
46 void get_min(LL &x,LL y) { if(y<x) x=y; }
47 
48 void solve() {
49     For(len,2,n) For(i,1,n-len+1) {
50         int j=i+len-1;
51         f[i][j][w[j]][w[j]]=f[i][j-1][0][0];
52         For(k,i,j-1) For(mi,1,sz) For(mx,mi,sz) 
53             get_min(f[i][j][min(mi,w[j])][max(mx,w[j])],f[i][k][mi][mx]+(k+1<=j-1?f[k+1][j-1][0][0]:0));
54         For(k,i,j) For(mi,1,sz) For(mx,mi,sz) 
55             get_min(f[i][j][0][0],f[i][k][mi][mx]+a+b*pf(ls[mx]-ls[mi])+(k+1<=j?f[k+1][j][0][0]:0));
56     }
57     printf("%lld
",f[1][n][0][0]);
58 }
59 
60 int main() {
61 #ifdef ANS
62     freopen(".in","r",stdin);
63     freopen(".out","w",stdout);
64 #endif
65     read(n);
66     read(a); read(b);
67     For(i,1,n) read(w[i]),ls[i]=w[i];
68     pre();
69     //For(i,1,n) printf("%d ",w[i]);
70     solve();
71     Formylove;
72 }

View Code

方块消除

应该算是上一道题的简化版。有了上一次的正解的转移这个就很好写了。思路差不多。$f[l][r][k]$（仅在$a[l]=a[r]$时有意义）表示l和r还没消除，从l到r包括l,r一共有k个和l,r同色的方块还没消除，其他的都消除完了的最大价值。g[l][r]表示l到r全部消除的最大价值。

 1 //Achen
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<vector>
 7 #include<cstdio>
 8 #include<queue>
 9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 const int N=207; 
16 typedef long long LL;
17 typedef double db;
18 using namespace std;
19 int T,n,a[N],f[N][N][N],g[N][N];
20 
21 template<typename T>void read(T &x)  {
22     char ch=getchar(); x=0; T f=1;
23     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
24     if(ch=='-') f=-1,ch=getchar();
25     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
26 }
27 
28 int main() {
29 #ifdef ANS
30     freopen(".in","r",stdin);
31     freopen(".out","w",stdout);
32 #endif
33     read(T);
34     For(cs,1,T) {
35         memset(f,128,sizeof(f));
36         memset(g,128,sizeof(g));
37         read(n);
38         For(i,1,n) read(a[i]);
39         For(i,1,n) g[i][i]=1,f[i][i][1]=0;
40         For(len,1,n) For(i,1,n-len+1) {
41             int j=i+len-1;
42             if(a[i]==a[j]) {
43                 For(k,i,j-1) if(a[k]==a[j]) {
44                     For(l,1,k-i+1) if(f[i][k][l]>=0) { 
45                         f[i][j][l+1]=max(f[i][j][l+1],f[i][k][l]+(k+1<=j-1?g[k+1][j-1]:0));    
46                     }
47                 }
48                 For(l,1,j-i+1) 
49                     g[i][j]=max(g[i][j],f[i][j][l]+l*l);
50             }
51             For(k,i,j-1) 
52                 g[i][j]=max(g[i][j],g[i][k]+g[k+1][j]);
53         }
54         printf("Case %d: %d
",cs,g[1][n]); 
55     }
56     Formylove;
57 }

View Code

之前还以为自己dp学的还可以，现在看来还是太肤浅了

「THUSC 2016」成绩单 & 方块消除 （区间dp）

「THUSC 2016」成绩单 & 方块消除（区间dp）