发表于 | 评论数：

题意求01矩阵第二大1矩阵的面积

真实被教育，求二大的题一般都很贱，求一大的值完全就是板子题，随便上网找找就行我这说说二大的要点。
首先错误的地方就是单调栈进去的都是当前最优的结果，所以我们会有一个hack的数据
1 4
1 1 1 1
答案显然是3但是我们会得到0…因为我们记录的都是当前最优最大的面积的矩形….
解决方法多加入一些长减一或者宽减一之类的矩形
然后就是寻找的时候好多bug,复杂的实现我就不说了,简易的实现就是把第一大面积第二大面积算出来然后再单调栈遍历一遍这个地方因为我们的复杂度大约n^2 1e6多点常数无所谓然后就是看看不重复的矩形的最大的面积是否会有多于一个等于最大值的有就直接输出最大值否则输出二大值即可.
矩形判重直接用左上角右下角坐标或者是i*m+j之类的判别
代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
long long st[1005],a[1005][1005],h[1005][1005],l[1005],r[1005],p,q;
set<int> s;
map<long long,map<long long,long long>> bk;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        char x;
        cin>>x;
        a[i][j]=x-'0';
    }
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
    if(a[j][i]==1)
    h[j][i]=h[j-1][i]+1;
    for(int i=1;i<=n;i++)
    {
        p=0;
        for(int j=1;j<=m;j++)
        {
            while(p&&h[i][st[p]]>=h[i][j])
            p--;
            if(p)
            l[j]=st[p];
            else
            l[j]=0;
            st[++p]=j;
        }
        p=0;
        for(int j=m;j;j--)
        {
            while(p&&h[i][st[p]]>=h[i][j])
            p--;
            if(p)
            r[j]=st[p];
            else
            r[j]=m+1;
            st[++p]=j;
        }
        for(int j=1;j<=m;j++)
        {
            s.insert((r[j]-l[j]-1)*h[i][j]);
            s.insert((r[j]-l[j]-2)*h[i][j]);
            s.insert((r[j]-l[j]-1)*(h[i][j]-1));
        }
    }
    auto it=s.end();
    int m1=*(--it);
    int m2=*(--it);
    int num__ = 0;
    for(int i=1;i<=n;i++)
    {
        p=0;
        for(int j=1;j<=m;j++)
        {
            while(p&&h[i][st[p]]>=h[i][j])
            p--;
            if(p)
            l[j]=st[p];
            else
            l[j]=0;
            st[++p]=j;
        }
        p=0;
        for(int j=m;j;j--)
        {
            while(p&&h[i][st[p]]>=h[i][j])
            p--;
            if(p)
            r[j]=st[p];
            else
            r[j]=m+1;
            st[++p]=j;
        }

        for(int j=1;j<=m;j++)
        {
            int now=(r[j]-l[j]-1)*h[i][j];
            if(now==m1&&(!bk[(i-h[i][j])*m+(l[j]+1)][(i-1)*m+(r[j]-1)]))
            {
                num__++;
                bk[(i-h[i][j])*m+(l[j]+1)][(i-1)*m+(r[j]-1)]=1;
            }
            if(num__>1)
            return printf("%d",m1),0;
        }
    }
    printf("%d",m2);
}

发表于 | 更新于 | 评论数：

技巧比较强，如果正着想删除几本书那实在是太难了，我是白给了。倒着想留下几本书的话，我们可以判断当前书在序列中是留下的第几本，那么很容易想到每一本都有可能由前面的任意序列组合而成，最后再枚举第三个剩下的条件然后即可解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int h,w;
}a[105];
int f[105][105],n,m,ans=1<<30;
bool cmp(node a,node b)
{
    return a.h<b.h;
}
int main()
{
    memset(f,0x3f,sizeof(f));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    f[i][1]=0;
    m=n-m;
    for(int i=1;i<=n;i++)
    scanf("%d%d",&a[i].h,&a[i].w);
    sort(a+1,a+1+n,cmp);
    for(int i=2;i<=n;i++)
    for(int j=1;j<i;j++)
    for(int k=2;k<=min(m,i);k++)
    f[i][k]=min(f[i][k],f[j][k-1]+abs(a[i].w-a[j].w));
    for(int i=m;i<=n;i++)
    ans=min(ans,f[i][m]);
    printf("%d",ans);
}

发表于 | 更新于 | 评论数：

很奇怪的dp，我是没有见过这种的之前，尤其是第二维倒着推，实际上就是把每种可能的分块情况枚举一遍,最后再输出答案,秒题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
int bk[1005],a[1005],p=0,f1[1005],f2[1005];
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    f1[1]=f2[1]=1;
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(int i=2;i<=n;i++)
    {
        f1[i]=1<<30;
        f2[i]=1<<30;
        memset(bk,0,sizeof(bk));
        int sum=0;
        for(int j=i;j;j--)
        {
            if(!bk[a[j]])
            {
                sum++;
                bk[a[j]]=1;
            }
            if(sum>k)
            break;
            f1[i]=min(f1[i],f1[j-1]+1);
            f2[i]=min(f2[i],f2[j-1]+sum);
        }
    }
    printf("%d\n%d",f1[n],f2[n]);
}

发表于 | 评论数：

概述

二分图判定很好说就是没有奇边环即可
然后就是匈牙利算法了匈牙利算法求的是最大匹配集根据一个定理这也等于最小点覆盖集

匈牙利算法

匈牙利算法原理是通过増广路实际上也不需要这么的复杂，核心在于我前面的两个点如果已经选了我再进行匹配的时候要怎么最优化
道理在于先维护一个vis代表当前点遍历过后所有的点,这个vis巧妙而且必不可少因为如果这是保证切换寻找的时候不会出现重复的现象

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
int n,m,k,l[105],r[105],mp[105][105],vis[105],ans;
int dfs(int p)
{
	for(int i=1;i<=m;i++)
	if(mp[p][i]&&!vis[i])
	{
		vis[i]=1;
		if(!r[i]||dfs(r[i]))
		{
			l[p]=i;
			r[i]=p;
			return 1;
		}
	}
	return 0;
}
int main()
{
	while(~scanf("%d%d%d",&n,&m,&k))
	{
		if(n==0)
		break;
		memset(mp,0,sizeof(mp));
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		for(int i=1;i<=k;i++)
		{
			int id,l,r;
			scanf("%d%d%d",&id,&l,&r);
			mp[l][r]=1;
		}
		ans=0;
		for(int i=1;i<=n;i++)
		{
			if(!l[i])
			{
				memset(vis,0,sizeof(vis));
				ans+=dfs(i);
			}
		}
		printf("%d\n",ans);
	}
}

最大权匹配集

匈牙利算法的升级版，应用于左右互相最大的匹配边权和最大值,匈牙利算法的重复尝试在于连接性这里要加上边权的问题
首先我们初始化左边的wl数组为边权最大的那条边的权值右边为0
接着我们每次匹配如果出现了问题，需要重复匹配按照这样的规则:
出现二夹一就要左加右减
最后把答案统计即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
int wl[305],wr[305],vl[305],vr[305],cha[305],n,a[305][305],vrr[305];
int dfs(int p)
{
	vl[p]=1;
	for(int i=1;i<=n;i++)
	{
		if(vr[i])
		continue;
		int g=wl[p]+wr[i]-a[p][i];
		if(g==0)
		{
			vr[i]=1;
			if(!vrr[i]||dfs(vrr[i]))
			{
				vrr[i]=p;
				return 1;
			}
		}
		else
		cha[i]=min(cha[i],g);
	}
	return 0;
}
int main()
{
	while(~scanf("%d",&n))
	{
		memset(wl,0,sizeof(wl));
		memset(wr,0,sizeof(wr));
		memset(vrr,0,sizeof(vrr));
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		scanf("%d",&a[i][j]);
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		wl[i]=max(wl[i],a[i][j]);
		for(int i=1;i<=n;i++)
		{
			memset(cha,0x7f,sizeof(cha));
			while(1)
			{
				memset(vl,0,sizeof(vl));
				memset(vr,0,sizeof(vr));
				if(dfs(i))
				break;
				int t=1<<30;
				for(int j=1;j<=n;j++)
				if(!vr[j])
				t=min(t,cha[j]);
				for(int j=1;j<=n;j++)
				{
					if(vl[j])
					wl[j]-=t;
					if(vr[j])
					wr[j]+=t;
					else
					cha[j]-=t;
				}
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++)
		ans+=a[vrr[i]][i];
		printf("%d\n",ans);
	}
}

发表于 | 更新于 | 评论数：

方程基本推对了就是转移的时候有点迷，实际上还要用f[i][j]=f[i-1][j]这样取min的时候才不会出错,然后就是就算越界也没事有点像背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int f[105][105],w1[105],w2[105];
int main()
{
    int a,b,c,d;
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    for(int i=1;i<=b;i++)
    scanf("%d%d",&w1[i],&w2[i]);
    for(int i=1;i<=b;i++)
    for(int j=0;j<=a;j++)
    {
        f[i][j]=f[i-1][j];
        for(int k=0;k<=min(j,w2[i]);k++)
        f[i][j]=min(f[i][j],f[i-1][j-k]+c+k*w1[i]);
    }
    if(f[b][a]>100000)
    printf("impossible");
    else
    printf("%d",f[b][a]);
}
0%