贪心

1.

poj2287

N匹马的田忌赛马问题

稳稳地赢。

寻找最优的方案。

更优的收益。

有时候,局部最优导致全局最优。

马的能力值。

使得让我赢的局数最多。

对于对方的任何一匹马,如果我的马能打败它,那么我就要用能打败它的马里面能力值最小的马去迎战,如果我的马不能打败它,那么我就用剩下的所有马中能力

最小的马去迎战。这个思路是很贪心的。

贪心不是一板一眼的算法,更是一种思路。

  

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int a[1010],b[1010];//田忌和齐王的马速序列
int main()
{
//#ifdef CDZSC_June
//freopen("in.txt","r",stdin);
//#endif
//std::ios::sync_with_stdio(false);
int n;
while(scanf("%d",&n),n)//输入田忌和齐王马的匹数
{
for(int i=1;i<=n;i++) scanf("%d",&a[i]);//输入田忌 n 匹马的速度
for(int i=1;i<=n;i++) scanf("%d",&b[i]);//输入齐王 n 匹马的速度
sort(a+1,a+1+n);//按照马速递增顺序排列田忌的 n 匹马
sort(b+1,b+1+n);//按照马速递增顺序排列齐王的 n 匹马

int tl=1,tr=n,ql=1,qr=n;//A 序列的首尾指针和 B 序列的首尾指针初始化
int sum=0;//田忌赢得的银币数初始化
while(tl<=tr)//若比赛未进行完
{
if(a[tl]<b[ql])//若田忌最慢的马慢于齐王最慢的马,则田忌最慢的马与齐王最快的马比,输一场
{
qr--;
tl++;
sum-=200;
}

else if(a[tl]==b[ql])//若田忌最慢的马与齐王最慢的马速度相同
{
while(tl<=tr && ql<=qr)//循环,直至田忌或齐王的马序列空为止
{
if(a[tr]>b[qr])//若田忌最快的马快于齐王最快马,则田忌最快的马与齐王最快的马比,赢一场
{
sum+=200;
tr--;
qr--;
}
else//否则若田忌最慢的马慢于齐王最快马,则田忌最慢的马与齐王最快的马比,输一场,退出 while
{
if(a[tl]<b[qr]) sum-=200;
tl++;qr--;break;
}
}
}

else//若田忌最慢的马快于齐王最慢的马,则田忌最慢的马与齐王最慢的马比,赢一场
{
tl++;
ql++;
sum+=200;
}
}
printf("%d\n",sum);
}
return 0;
}

2.

括号序列配对问题。

把一个问题的本质看透。

缺x个左括号的只能和缺x个右括号的去配对连接。只有这样它才一定生成合法的括号序列。

3.

RGB序列问题。

Red,Green,Blue.

可以从动态规划的方法来解决问题哦!

我们用贪心算法不是盲目贪心的哦!我们的贪心是能得到最优解的。有时候盲目去贪的话,还真让你贪对了。

贪心算法的理论证明是非常晦涩难懂的!

怎么贪也是一种学问哦!

博弈(game):

游戏就是对战!

在五子棋中,执黑先行,先手必胜。

1.

石子博弈。

谁先没得取谁就输了。

先手,后手。

枚举-----》》推出结论

我们可以先模拟一下哦。

先手必败的情形:n是3的倍数!

必胜态&&必败态。

必胜态的话是存在一个操作将必胜态转移到必败态的;必败态则是任何操作都只能从必败态转移到必胜态!

2.

取数博弈。

一直都是假设两个人都能做出最明智的决策。

先考虑必败态:只要所有

后手通过模仿先手的决策败先手之!

再考虑必胜态!

实现从必胜态到必败态的一种转移。

当然,博弈有很多有趣的问题!

谢谢a兵长老师的讲解!

05-26 00:10