傳送門
題意：
思路： 按照貪心的思路來考慮的話，顯然是每一列111的個數越多越好，所以我們能放到一列就放到一列。設f[l][r]f[l][r]f[l][r]為在[l,r][l,r][l,r]內，區間全部都在里面的貢獻。顯然這個貢獻就是全部落在[l,r][l,r][l,r]內區間的個數平方。假設當前點為k(l<=k<=r)k(l<=k<=r)k(l<=k<=r)，那么f[l][r]=max(f[l][r],f[l][k?1]+f[k+1][r]+S[l][r][k])f[l][r]=max(f[l][r],f[l][k-1]+f[k+1][r]+S[l][r][k])f[l][r]=max(f[l][r],f[l][k?1]+f[k+1][r]+S[l][r][k])其中S[l][r][k]S[l][r][k]S[l][r][k]表示經過第kkk列，左右端點在[l,r][l,r][l,r]內的個數。這個式子顯然可以用區間dp來求解。因為我們定義的f[l][r]f[l][r]f[l][r]為區間全部落在[l,r][l,r][l,r]這個區間內，我們枚舉kkk，將區間經過kkk的區間都加到sumsumsum里，再分成[l,k?1],[k+1,r][l,k-1],[k+1,r][l,k?1],[k+1,r]的子問題的時候，這兩部分已經計算過的值中一定不含經過kkk的區間因為他們包含的是左右端點全都在[l,k?1],[k+1,r][l,k-1],[k+1,r][l,k?1],[k+1,r]中的區間貢獻，可以合并。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=110,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
,m
;
int a
[N
][N
],b
[N
][N
];
int f
[N
][N
];int main()
{
scanf("%d%d",&n
,&m
);for(int i
=1;i
<=n
;i
++){int k
; scanf("%d",&k
);while(k
--){int l
,r
; scanf("%d%d",&l
,&r
);for(int j
=l
;j
<=r
;j
++) a
[j
][i
]=l
,b
[j
][i
]=r
;}}for(int len
=1;len
<=m
;len
++){for(int l
=1;l
+len
-1<=m
;l
++){int r
=l
+len
-1,sum
=0;for(int i
=l
;i
<=r
;i
++){sum
=0;for(int j
=1;j
<=n
;j
++) if(a
[i
][j
]>=l
&&b
[i
][j
]<=r
) sum
++;f
[l
][r
]=max(f
[l
][r
],f
[l
][i
-1]+f
[i
+1][r
]+sum
*sum
);}}}printf("%d\n",f
[1][m
]);return 0;
}
總結
以上是生活随笔為你收集整理的Codeforces Round #655 (Div. 2) E. Omkar and Last Floor 区间dp + 巧妙的状态设计的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
