糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

POJ 1171 Letter Game 背包

思路:

它的要求是,给你几个字母,用这些字母拼几个字典里面有的单词,所有单词加起来求最高得分。
转化一下,就是个01背包问题。
由于单词的长度很短很短了,只有3~7个字母,所以总状态数很少啦。数组开到 2048 就可以AC了。

后来又搜了一下别人的解题报告哦,发现有个哥们很牛逼。
他说:单词长度范围在3--7内。所以可能的词组 只能是 3+3 或 3+4

一语惊醒脑残人。太牛逼了!

代码 150ms AC。

#include <stdio.h>

char key[] = {
    
"qwertyuiop"
    
"asdfghjkl"
    
"zxcvbnm"
}
;
int score[] = {
    
7612254135,
    
214655763,
    
7746525
}
;

int map[256], col[256], idx[256], mul[8], tot[8], cnt, hash[2048], top;

int can_add(int a, int b)
{
    
int i, ia, ib;

    
for (i = 1; i < cnt; i++{
        ia 
= (a / mul[i - 1]) % tot[i];
        ib 
= (b / mul[i - 1]) % tot[i];
        
if (ia + ib >= tot[i])
            
return 0;
    }


    
return 1;
}


int main()
{
    
int i, val, sum[256], sc;
    
char str[16];

    freopen(
"e:\\test\\in.txt""r", stdin);

    
for (i = 0; i < 26; i++)
        map[key[i]] 
= score[i];
    
    scanf(
"%s", str);
    
for (i = 0; str[i]; i++)
        col[str[i]]
++;

    cnt 
= 1;
    
for (i = 'a'; i <= 'z'; i++)
        
if (col[i]) {
            idx[i] 
= cnt;
            mul[cnt] 
= tot[cnt] = col[i] + 1;
            cnt
++;
        }


    mul[
0= 1;
    
for (i = 1; i < cnt; i++)
        mul[i] 
*= mul[i - 1];
    top 
= mul[cnt - 1];
    hash[
0= 1;

    
while (scanf("%s", str), str[0!= '.'{
        
for (i = 'a'; i <= 'z'; i++)
            sum[i] 
= 0;
        sc 
= 0;
        val 
= 0;
        
for (i = 0; str[i]; i++{
            sum[str[i]]
++;
            
if (sum[str[i]] > col[str[i]])
                
break;
            sc 
+= map[str[i]];
            val 
+= mul[idx[str[i]] - 1];
        }

        
if (str[i])
            
continue;
        
for (i = top; i >= 0; i--{
            
if (!hash[i])
                
continue;
            
if (can_add(i, val) && hash[i + val] < hash[i] + sc)
                hash[i 
+ val] = hash[i] + sc;
        }

    }


    sc 
= 0;
    
for (i = top; i >= 0; i--)
        
if (hash[i] > sc)
            sc 
= hash[i];
    printf(
"%d\n", sc - 1);

    
return 0;
}

posted on 2010-05-10 21:37 糯米 阅读(499) 评论(0)  编辑 收藏 引用 所属分类: POJ


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理