oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

说题~

Posted on 2008-08-17 10:09 oyjpart 阅读(2650) 评论(1)  编辑 收藏 引用 所属分类: ACM/ICPC或其他比赛

PKU2690 Yahtzee

用搜索做,超时,郁闷。

正解:动态规划。

DP状态:dp[mask][i], mask代表用了多少种方案了,i代表前6种方案的得分。

因为前6种方式得分和超过63有加分,因此这一维是必须的。

DP向后推比较好写。

核心代码:

    memset(dp, -1sizeof(dp));
    dp[
0][0= 0;
    pre[
0][0][0= -1;
    
for(j = 0; j < (1<<13); ++j) {
        
int round = ones(j);
        
for(k = 0; k < 126++k) if(dp[j][k] != -1) {
            
for(o = 1; o < 14++o) if(!(j&(1<<(o-1)))) {
                
int add = 0;
                
if(o <= 6) add = s[round][o];
                
if(dp[j|(1<<(o-1))][k+add] < dp[j][k] + s[round][o]) {
                    dp[j
|(1<<(o-1))][k+add] = dp[j][k] + s[round][o];
                    pre[j
|(1<<(o-1))][k+add][0= o;
                    pre[j
|(1<<(o-1))][k+add][1= s[round][o];
                }
            }
        }
    }
    
int max = -1, maxa = -1, maxb = -1, maxk; 
    
for(i = 0; i < (1<<13); ++i) {
        
for(k = 0; k < 126++k) {
            
int now = dp[i][k];
            
if(k >= 63) now += 35;
            
if(now > max) {
                max 
= now;
                maxa 
= i;
                maxb 
= k;
                
if(k >= 63) maxk = 35;
                
else maxk = 0;        
            }
        }
    }


Feedback

# re: 说题~  回复  更多评论   

2008-08-17 17:37 by dell笔记本
我给存起来了,以后要是能变成一本电子书就好了。

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理