Codeforces Round 655 (Div. 2) E

• 题意

  • 给出一个 (n*m) 的地板，每一行会被分为多个隔间，每个隔间只能有一个 1 ，其余都是 0 。我们定义地板的质量为每列值的和的平方和。
  • 

• 解析

  • 首先 (n,m) 都比较小，我们可以用区间dp 。
  • 根据区间dp 的常见形式，可以写出其状态转移方程 (dp[i][j] = max(dp[i][k-1] + f(k) + dp[k+1][j]))
  • 我们现在需要考虑，在区间 ((i,j)) 中，如何计算 (f(k)) 的值。
  • 显然(?)只有 (k) 所在的隔间在整个 区间((i,j))内才能计算答案

• 代码

  • #include<bits/stdc++.h>
    
    using namespace std;
    
    const int Maxn = 110;
    
    int a[Maxn][Maxn],b[Maxn][Maxn],dp[Maxn][Maxn];
    
    int main(){
        int n,m;
        scanf("%d %d",&n,&m);
        for(int i=1,k;i<=n;i++)
        {
            scanf("%d",&k);
            for(int j=1,l,r;j<=k;j++)
            {
                scanf("%d %d",&l,&r);
                for(int p=l;p<=r;p++) 
                    a[i][p] = l,b[i][p] = r;
            }
        }
        for(int len = 1; len <= m; len++)
        {
            for(int l=1; l+len-1 <= m; l++)
            {
                int r = l+len-1;
                for(int k=l; k<=r; k++)
                {
                    int tmp = 0;
                    for(int i=1;i<=n;i++)
                        if( l <= a[i][k] && b[i][k] <= r )
                            tmp++;
                    dp[l][r] = max(dp[l][r],dp[l][k-1] + tmp*tmp + dp[k+1][r]);
                }
            }
        }
        cout<<dp[1][m]<<endl;
        return 0;
    }