H-Second Large Rectangle

题意：

输入一个n*m的矩阵，矩阵由字符0和1组成，需要你找到第二大的全为1的矩阵的大小

分析：

将n*m的矩阵转化为n个以i为底的直方图，利用单调栈分别对每个直方图进行求解，找出次大值

前置知识：单调栈、相似习题：POJ 2559  POJ3494（）

代码：

#include
      
       #include
       
        #include
        
         using namespace std;const int MAX=1009;int n,m;int max1,max2;char ch[MAX][MAX];int cnt[MAX][MAX];struct node{    int height,left;    node(){}    node(int a,int b){        height=a,left=b;    }};stack
         
          st;void check(int x){    if(x>max1){        max2=max1;        max1=x;    }    else if(x>max2)        max2=x;}int main(){    max1=0,max2=0;    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)        scanf("%s",ch[i]+1);    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)            if(ch[i][j]=='1')                cnt[i][j]=cnt[i-1][j]+1;        for(int i=1;i<=n;i++)    {        for(int j=1;j<=m;j++)        {            int p=j;            while(!st.empty()&&st.top().height > cnt[i][j])            {                check(st.top().height*(j-st.top().left));                check((st.top().height-1)*(j-st.top().left));                check(st.top().height*(j-st.top().left-1));                //cout<<"**"<
          
           <<' '<
           
            <
           
          
         
        
       
      

 

F-Partition problem

题意：

将2N个人分成均为N的两队人，一队的人i对另一队的每个人都存在一个贡献vi,j，求贡献和最大

分析：

直接暴力搜索每种情况即可QAQ

代码：

#include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;const int MAX=40;int val[MAX][MAX],t1[MAX],t2[MAX];int n;ll ans;void dfs(int pos,int cnt1,int cnt2,ll sum){    if(cnt1==cnt2&&cnt1==n)    {        ans=max(ans,sum);   //取最大值        return;    }    ll temp=0;    if(cnt1