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

简约的一道dp小品好题，推着推着发现是一个交错的0,1数列，接着脑子就开始发晕不知道怎么能做的又快又好，看了题解之后发现每次只需要如果有大小变化就交错更新即可否则按照原样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
int f[100005][3],a[100005];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    f[i][0]=f[i][1]=1;
    for(int i=2;i<=n;i++)
    {
        if(a[i]<a[i-1])
        f[i][0]=f[i-1][1]+1;
        else
        f[i][0]=f[i-1][0];
        if(a[i]>a[i-1])
        f[i][1]=f[i-1][0]+1;
        else
        f[i][1]=f[i-1][1];
    }
    printf("%d",max(f[n][0],f[n][1]));
}

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

概述

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

匈牙利算法

匈牙利算法原理是通过増广路实际上也不需要这么的复杂，核心在于我前面的两个点如果已经选了我再进行匹配的时候要怎么最优化
道理在于先维护一个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);
	}
}

发表于 | 评论数：
博弈小游戏

发表于 | 评论数：

博弈小游戏

开始

制作详情

NIM博弈经典小游戏,尝试着去击败电脑吧!!!!

返回

游戏的规则相当的简单，现在桌上有5堆硬币，每一个回合当前的玩家需要任选一堆拿走至少一个硬 币，不能当前回合一个不拿，谁拿走最后一个硬币谁就获胜，现在请你选择你的先后手顺序。

试着挑战我精心准备的AI吧！！！

先手

后手

回合

重新来过?

0%