注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

状态还可以这样存储~  

2009-07-29 11:18:11|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Card Game
Time Limit: 1000MS  Memory Limit: 65536K
Total Submissions: 213  Accepted: 41

Description
Many of you may have played a card game called "Card Erasing". Such type of game have different variations and one is available on the Little Game Center of
www.xiaonei.com.

Generally, in such games, a player can get points by eliminating cards from a certain bulk. For simplicity, let us use integer 1 to 13 to represent cards Ace, Two, … , Queen and King. Starting at a base card with integer number X, one can eliminate a card that is adjacent to the base card, which means the number of that card should be X-1 or X+1. In addition, King and Ace are considered to be adjacent with each other. After eliminating a card, this card will replace the base card in the next turn. Now Facer is quite interested in one such card game and he wants to maximize his points. He told the rules of this game to Dzx and now our great Dzx is asking you to help him. There are n×(n+1)/2 cards to be eliminated, arranging in the order as below:

状态还可以这样存储~ - chhaj5236 - chhaj5236的博客状态还可以这样存储~ - chhaj5236 - chhaj5236的博客

Only the cards that have not been covered can be took away. So at first only cards on the last row satisfied such condition. If more than one card can be eliminated at a time, the player can choose any one. The player has m chances to refresh the base card, replacing it by a randomly generated card. The player can refresh the base card at any time, for example, when no move can be made. The game is over when all cards have been eliminated, or no move can be made and there are no more chances to refresh cards. Each time a player eliminates a card, he gets P points, but the player losts Q points if he refresh the base card. Thus the total points the player got may be negative. To make this game even easier, let us suppose all n×(n+1)/2 cards are known before eliminating them. You are given the starting state of this game, please determine the maximum expectation of the points Facer could get.

Input

The input contains several test cases.
For each test case, two integers n, m are iven in the first line.
The second line contains n×(n+1)/2 numbers depicting the bulk of cards. The cards are given from top to bottom, and from left to right when they are in the same row. The last line of each test case are the integers P, Q, and X, where X represents the initial base card. The input file ends with two zeroes. (1≤n≤5, 0≤m≤100, 0≤P, Q≤100)

Output

For each test case, print the maximum expectation of points in a separate line, rounded to the second digit after the decimal point.

Sample Input

2 1
10 1 2
100 0 7
0 0
Sample Output

61.54
Hint

The sample has three cards and only one chance to refresh base card.
At first only the cards on the last row, 1 and 2 can be eliminated. As the base card is 7, no move can be made without refreshing the base card.
If the base card becomes 13, 1, 2 or 3 after refreshing, Facer can took away the two cards on the last row, getting 200 points and then the game is over. Otherwise the game will be over with 0 points.
So the expectation is 200*(4/13) + 0*(9/13).
Source

PKU Campus 2009 (POJ Monthly Contest – 2009.05.17), Asukalt

题目大意:给定牌面(摆放方式如图),并给定一张底牌。玩牌的人可以从没有被其他纸牌覆盖的牌中,选择一个与底牌相邻的移除掉,并得到一定的分数P,之后底牌更新为被移除的牌。相邻在这里被定义为与底牌差1的牌,其中Ace和King认为是相邻的。如果当前符合条件的纸牌中没有和底牌相邻的,那么玩家还有m次更新底牌的机会,每更新一次扣除分数Q,更新的规则是从Ace到King随机产生一张纸牌作为新的底牌。现在给定了牌面,初始的底牌,以及分数P、Q和更新的机会m次,求得到分数的最大期望值是多少。

主要思想:

1.先不考虑更新底牌的机会,给定牌面和底牌之后,根据牌面可以得到当前可能被移除的牌,并分别与底牌进行比较,如果符合相邻的标准,就将底牌更新,同时将该牌移除牌面。如果有多张牌符合移除的规则,那么从中移除可以得到的分数最多的一张牌。之后,再用剩下的牌面和更新后的底牌进行上述相同的操作。很明显,这是一个递归的过程。

2.现在我们再考虑加入了更新的机会,情况会怎么样。根据题目的意思,更新底牌是可以在任意时刻进行的。也就是说就算现在有移除一张牌的机会存在,也可以选择不移除,而是更新底牌以获得更高的期望分数。所以在上面的递归过程中的每一个阶段中还要加入一个处理。只要有机会更新底牌,就尝试着更新底牌,如果这样能够得到更高的期望分数,则执行更新操作。

3.根据上面的思想所写的递归程序在没有任何处理的情况下会超时。因为更新底牌的机会如果过多的话,会导致大量的重复计算,所以这里要有一个记忆化的处理。为了要实现记忆化,我们就要找出能够唯一标示当前状态的几个参数。而当前的牌面,更新的机会数,底牌这三个参数就能够唯一的标示一个状态。最直观的做法就是15张牌最多2^15中状态,所以可以定义dp[32770] [101] [14]来存储已经计算过的状态值,但是会MLE,因为dp所占空间实在是太大了。更新的机会数和底牌已经是最小了,那么我们要考虑的就是如何降低状态数。对于每张牌来说,只有其下面的两张牌被移除了,才有可能移除这张牌,从这点出发我们可以将一个牌面逆时针翻转一下,比如Sample Input中的
 10
1   2
变成:
10 2
   1
然后我们再统计每一行的牌数,正如之前所说,只要2存在10就不可能被移除,所以每一行的牌数如果固定,那么这一行的扑克牌也就固定了。这样每一行牌的数目根据题意一定小于等于5,我们将每一行得到的数作为六进制中的一位就可以得到唯一对应的一个十进制数了。那么做大状态数就是5+4*6+3*6^2+2*6^3+6^4=1865,那么我们用dp[1867] [101] [14]就可以存储所有的状态了。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#define MAX 25
using namespace std;
struct Card{
    int num;
    int l,r;
};   //存储牌面,l和r分别指向该牌下面的两张牌
Card card[MAX];
double dp[2000][101][14];    //记忆化存储
bool visit[2000][101][14];
double p,q;
int w[5]={1,6,36,216,1296};   //六进制对应的权值
double score(int times,int level,int n,int chances,int base);
int main(){
    int n,m,x,num;
    int i,j;
    double result;
    while(scanf("%d%d",&n,&m),n!=0||m!=0){
        num=(n*(n+1))>>1;
        for(j=1;j<=n;j++){     //按层输入牌面,并处理每张牌下面的牌在数组中位置
            for(i=((j*(j-1))>>1)+1;i<=(j*(j+1))>>1;i++){
                scanf("%d",&card[i].num);
                card[i].l=i+j;
                card[i].r=i+j+1;
                if(j==n)card[i+j].num=card[i+j+1].num=0;   //将最后一排的l和r都置为0,表示下面没有牌
            }
        }
        scanf("%lf%lf%d",&p,&q,&x);
        memset(visit,0,sizeof(visit));
        result=score(0,n,num,m,x);
        printf("%.2lf\n",result);
    }
    return 0;
}
double score(int times,int level,int n,int chances,int base){
    if(times==n)return 0;
    int i,j=0,k;
    int set[MAX],s[5],state=0;
    memset(s,0,sizeof(s));
    for(i=1;i<=level;i++){
        for(k=((i*(i-1))>>1)+1;k<=(i*(i+1))>>1;k++){//将有可能被除掉的牌放到数组set中,并计算翻转后每一层的牌数
            if(card[k].num&&!card[card[k].l].num&&!card[card[k].r].num)set[j++]=k;
            if(card[k].num)s[((i*(i+1))>>1)-k]++;
        }
    }
    for(i=1;i<=level;i++)state+=s[i-1]*w[i-1];   //计算牌面转换后的值
    if(visit[state][chances][base])return dp[state][chances][base];
    bool first=true;
    int store;
    double temp,max=0;
    for(i=0;i<j;i++){    //查看所有符合条件的牌,并选出得分期望最高的
        if((int)abs((double)(base-card[set[i]].num))==1||(int)abs((double)(base-card[set[i]].num))==12){
            store=card[set[i]].num;
            card[set[i]].num=0;
            if(first){
                max=p+score(times+1,level,n,chances,store);
                first=false;
            }
            else{
                temp=p+score(times+1,level,n,chances,store);
                if(max<temp)max=temp;
            }
            card[set[i]].num=store;
        }
    }
    if(!chances){   //如果没有更新底牌的机会就直接返回
        dp[state][chances][base]=max;
        visit[state][chances][base]=true;
        return max;
    }
    double sum=0;
    for(i=1;i<=13;i++){    //如果有更新的机会,就试着更新
        sum+=score(times,level,n,chances-1,i);
    }
    sum=sum/(double)13-q;
    if(!first&&sum<max)sum=max;   //选出得分期望最大的
    dp[state][chances][base]=sum;
    visit[state][chances][base]=true;
    return sum;
}

后记:

1.由于受到之前思想的影响,只是简单增加了计算牌面的代码,而没有进一步简化代码,其实在传参的时候已经不需要前面的参数了,而是直接将计算后的s数组最为参数传进去就可以了。而且刚开始在输入的同时就可以实现翻转的操作,这样就可以省去每次递归都要算一遍s数组。

2.这里状态存储的思想确实精辟,要多多钻研钻研。

3.之前一直WA掉的原因是在更新底牌的操作那里,在更新时如果有牌可以移除我就直接移除了,却不记得这时候还是可以不移除而继续更新底牌的,导致了结果偏小。这里其实还有一个疑惑,难道不是没牌的时候才更新底牌得到的分才可能是最大的吗?可能是因为这里更新底牌的时候存在一定概率的原因,而且这道题目算的是得分的期望值最大,如果没有概率的话,才会是我所想的那样吧。

  评论这张
 
阅读(272)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017