·天新网首页·加入收藏·设为首页·网站导航
数码笔记本手机摄像机相机MP3MP4GPS
硬件台式机网络服务器主板CPU硬盘显卡
办公投影打印传真
家电电视影院空调
游戏网游单机动漫
汽车新车购车试驾
下载驱动源码
学院开发设计
考试公务员高考考研
业界互联网通信探索
您现在的位置:天新网 > 软件开发
UVA 10029 - Edit Step Ladders(记忆化搜索)
http://www.21tx.com 2014年01月20日 CSDN 帆帆帆帆帆帆帆帆帆帆

问题B.糖果的

存在的问题

小鲍勃是玩游戏。他想赢得一些糖果 - 尽可能多。

有4根桩,每根桩包含N糖果。鲍勃是一篮子可容纳最多5糖果。每次,他把糖果放进篮筐顶部的一堆,如果是两个相同颜色的糖果,他可以把他们两个外线篮子,并把它们纳入自己的口袋。当篮子里装满的,没有两个相同颜色的糖果,游戏结束。如果游戏是完美的发挥,本场比赛将结束没有留在成堆的糖果。

例如,鲍勃玩这个游戏是这样的(N = 5):

UVA 10029 - Edit Step Ladders(记忆化搜索)

需要注意的是不同的数字表示不同的颜色,有20种颜色编号1 .. 20。

'好像这么辛苦......“鲍勃很疑惑了。糖果的多少对他带回家最多?

输入

的输入,将包含不超过10个的测试用例。每个测试案例开始行包含一个整数N(1 <= N <= 40),代表桩的高度。在接下来的n行,每行包含四个整数XI1,XI2,常作形容词,戏(范围在1 .. 20)。每个整数表示的颜色对应的糖果。测试包含n = 0的情况将终止输入,这种情况下你不应该给一个答案。

输出

糖果,巧小的孩子可以带回家的对数输出。每个测试用例一行打印你的答案。

采样输入

5
1 2 3 4
1 5 6 7
2 3 3 3
4 9 8 6
8 7 2 1
1
1 2 3 4
3
1 2 3 4
5 6 7 8
1 2 3 4
0

样本输出

8
0
3

题意: 有4堆糖果,每堆有n个,每堆能从最上面取,放到一个篮子里,篮子容量是5,如果篮子里有相同的糖果,则这一对糖果可以放进口袋里,求出最多能放几对到口袋里

思路:记忆化搜索,开一个四维数组表示每堆当前个数来记录状态。

代码:

#include <stdio.h> 
#include <string.h> 
    
int n, candy[45][4], i, j, k, l, ans, vis[25], top[4], dp[45][45][45][45]; 
    
void dfs(int sum, int count) { 
    if (count == 5 || (top[0] == n && top[1] == n && top[2] == n && top[3] == n)) { 
        if (ans < sum) 
            ans = sum; 
        return; 
    } 
    for (int i = 0; i < 4; i ++) { 
        if (top[i] == n) continue; 
        int sb = candy[top[i]][i]; 
        top[i] ++; 
        if (vis[sb] && dp[top[0]][top[1]][top[2]][top[3]] < sum + 1) { 
            dp[top[0]][top[1]][top[2]][top[3]] = sum + 1; 
            vis[sb] = 0; 
            dfs(sum + 1, count - 1); 
            vis[sb] = 1; 
        } 
        else if (!vis[sb] && dp[top[0]][top[1]][top[2]][top[3]] < sum) { 
            dp[top[0]][top[1]][top[2]][top[3]] = sum; 
            vis[sb] = 1; 
            dfs(sum, count + 1); 
            vis[sb] = 0; 
        } 
        top[i] --; 
    } 
} 
    
int main() { 
    while (~scanf("%d", &n) && n) { 
        memset(top, 0, sizeof(top)); 
        memset(vis, 0, sizeof(vis)); 
        memset(candy, 0, sizeof(candy)); 
        ans = 0; 
        for (i = 0; i <= n; i ++) 
            for (j = 0; j <= n; j ++) 
                for (k = 0; k <= n; k ++) 
                    for (l = 0; l <= n; l ++) 
                        dp[i][j][k][l] = -1; 
        for (i = 0; i < n; i ++) { 
            for (j = 0; j < 4; j ++) { 
                scanf("%d", &candy[i][j]); 
                } 
            } 
        dfs(0, 0); 
        printf("%dn", ans); 
    } 
    return 0; 
}

上一篇: UVA 590 Always on the run(dp)
下一篇: UVA 10280 Old Wine Into New Bottles(dp完全背包)

关于我们 | 联系我们 | 加入我们 | 广告服务 | 投诉意见 | 网站导航
Copyright © 2000-2011 21tx.com, All Rights Reserved.
晨新科技 版权所有 Created by TXSite.net