2019牛客暑期多校第二场题解FH

F.Partition problem

传送门

题意：有2n个人，分两组，每组n个，要求sum(v)最大值。

题解：n并不大我们可以枚举每个人是在1组还是2组爆搜。

代码：

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N =  + ;

int n,a[N],b[N];

ll v[N][N],ans = ,cnt1=,cnt2=;

void dfs(int x,ll sum) {

    if (cnt1>n||cnt2>n) return;

    if (cnt1==n&&cnt2==n) {

        ans = max(ans,sum);

        return;

    }

    if (cnt1 < n) {

        a[++cnt1] = x;

        for (int i = ; i <= cnt2; i++)

            sum += v[x][b[i]];

        dfs(x+,sum);

        for (int i = ; i <= cnt2; i++)

            sum -= v[x][b[i]];

        cnt1--;

    }

    if (cnt2 < n) {

        b[++cnt2] = x;

        for (int i = ; i <= cnt1; i++)

            sum += v[x][a[i]];

        dfs(x+,sum);

        for (int i = ; i <= cnt1; i++)

            sum -= v[x][a[i]];

        cnt2--;

    }

}

int main() {

    scanf("%d",&n);

    for (int i = ; i <= *n; i++)

        for (int j = ; j <= *n; j++)

            scanf("%lld",&v[i][j]);

    dfs(,);

    printf("%lld\n", ans);

    return ;

}

H.Second Large Rectangle

传送门

题意：给你一个n*m的01矩阵，问全为1的第二大的矩阵大小。

题解：这题相当于从第1行到第n行，以当前行为底求直方图的第二大面积。我们知道怎么求直方图的最大面积（不知道的点这里）。我们可以用单调栈来做。不过要注意第二大不一定是用求最大的方法找到的第二大，也可能是最大的减去一行或者一列的大小。（因为没注意到这个WA了）。

代码：

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1e3 + ;

char s[N];

int dp[N][N];

int main() {

    int n,m;

    scanf("%d%d",&n,&m);

    int max1 = ,max2 = ,area;

    for (int i = ; i <= n; i++) {

        scanf("%s",s);

        stack<int> v;

        for (int j = ;j <= m; j++) {

            if(j == m) dp[i][j] = -;

            else {

                dp[i][j] = s[j]==''?:;

                dp[i][j] += dp[i][j]*dp[i-][j];

            }

            if (v.empty() || dp[i][j] > dp[i][v.top()])

                v.push(j);

            else {

                int now = v.top();

                v.pop();

                if (v.empty()) area = j * dp[i][now];

                else area = (j - v.top() - ) * dp[i][now];

                if(area > max1) {

                    max2 = max1;

                    max1 = area;

                    //注意这里

                    if (v.empty())

                        max2 = max(max2,max(area - dp[i][now],area-j));

                    else max2 = max(max2,max(area - dp[i][now],area-(j - v.top() - )));

                }else if (area > max2) max2 = area;

                j--;

            }

        }

    }

    printf("%d\n", max2);

    return ;

}