欢迎 rukelee 加入本站!
 免费注册  用户登陆  汇款方式  汇款确认  产品报价  联系我们  帮助中心
加入收藏
设为首页
会员体系
申请VIP
网站首页 光盘超市 软件下载 技术文章 专题 用户中心 VIP会员 技术论坛 网站留言 娱乐中心 卓越资源
今天是:2008年11月21日 星期五  您现在位于: 首页 → 技术文章 → 多边形游戏的动态规划解...
   多边形游戏的动态规划解法
作者:raincatss  出处:raincatss.cublog.cn  更新时间: 2007年05月31日 
多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。
游戏第1步,将一条边删除。
随后n-1步按以下方式操作:
(1) 选择一条边E以及由E连接着的两个顶点V1和V2;
(2) 用一个新的顶点取代边E以及由E连接着的两个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。
最后,所有边都被删除,游戏结束。游戏的得分就是所剩顶点上的整数值。
问题:对于给定的多边形,计算最高得分。
 
该问题是动态规划中的一个典型问题,具体解法如下:
 

#include <stdio.h>
#include <ctype.h>

#define N 5

char op[N];
int minf, maxf, m[N][N][2];
void PolyMax();
void MinMax(int i, int j, int k);

int main(int argc, char* argv[])
{
    int i;
    char ch;

    for (i = 0; i < N; i ++) {
        scanf("%d", &m[i][0][0]);
        m[i][0][1] = m[i][0][0];
        while((ch = getchar()) && isspace(ch));
        op[i] = ch;
    }

    PolyMax();

    return 0;
}

void PolyMax()
{
    int i, j, k, max;

    for (j = 1; j < N; j ++)
        for (i = 0; i < N; i ++)
            for (k = 0; k < j; k ++) {
                MinMax(i, j, k);
                if (m[i][j][0] > minf) m[i][j][0] = minf;
                if (m[i][j][1] < maxf) m[i][j][1] = maxf;
            }

    max = m[0][N - 1][1];
    for (i = 1; i < N; i ++)
        if (max < m[i][N - 1][1]) max = m[i][N - 1][1];

    printf("%d\n", max);
}

void MinMax(int i, int j, int k)
{
    int e[4], l,
        a = m[i][k][0],
        b = m[i][k][1],
        r = (i + k + 1) % N,
        c = m[r][j - k - 1][0],
        d = m[r][j - k - 1][1];

    if (op[(r - 1 + N) % N] == '+') {
        minf = a + c;
        maxf = b + d;
    } else {
        e[0] = a * c;
        e[1] = a * d;
        e[2] = b * c;
        e[3] = b * d;
        minf = e[0];
        maxf = e[0];
        for (l = 1; l < 4; l ++) {
            if (minf > e[l]) minf = e[l];
            if (maxf < e[l]) maxf = e[l];
        }
    }
}

 (本文已被浏览 2736 次)
 发布人:sdccf
 → 推荐给我的好友
上篇文章:简要安装 FreeBSD 6.2 及配置桌面环境
下篇文章:不用临时变量交换两个数的值
 相关文章:
SCO OpenServer 5.0.7制作紧急启动光盘的方法 将SCO OpenServer 5.0.6安装到IBM X3650上
如何把一个软盘镜像HBA文件转光盘ISO格式HBA文件 SCO操作系统安装Serial ATA (SATA)硬盘的方式
ubuntu 8.04 上安装 oracle 10g sco unix 5.07 使用windows FAT 格式的USB盘过程
制作带有hpsas驱动的SCO5.0.6应急和引导光盘安装G5 联想扬天M2600C安装SCO5.0.6+Windows XP
万年历的C语言程序 Sco UNIX的核心引导过程详解
Fedora 7一共有3种类型的Live镜像 Fedora 7下玩游戏
优化Fedora 7,关掉不需要的Fedora services Linux 下 C 语言编程
C语言常见错误 在centos 5中使用xfce桌面环境
C语言中用qsort()快速排序 不使用逻辑运算求得两数的最大值
C语言中用bsearch()实现查找操作 判断无符号整数的二进制表示中1的个数

相关搜索
查看百度中关于多边形游戏的动态规划解法的更多内容
查看google中关于多边形游戏的动态规划解法的更多内容
   文章分类
操作系统 |
SCO_UNIX  Sun_Solaris  IBM_AIX  HP_UX  Linux  BSD  Tru64_UNIX 
通用UNIX知识  Windows  Minix 
程序设计 |
Shell编程  C/C++  汇编  PHP  JAVA  Perl  Python 
ASP/HTML  XML  中间件 
数据库 |
Oracle  Informix  Sybase  Fox  DB2  SQL  MySQL 
PostgreSQL 
网络应用 |
网络应用 
计算机硬件 |
计算机主机  打印机  路由器  交换机  终端  磁带机  MO 
刻录机  终端服务器  调制解调器 
   文章评论
  → 评论内容 (点击查看)   共0条评论,每页显示5条评论   浏览所有评论
(没有相关评论)
  → 发表我的评论
您的姓名: 您的Email:
评论内容:
250字内
发表评论:      发表评论须知 →
  • 尊重网上道德,遵守《全国人大常委会关于维护互联网安全的决定》及中华人民共和国其他各项有关法律法;
  • 本站有权保留或删除您发表的任何评论内容;
  • 关于我们 ┋  网站留言 ┋  网站地图 ┋  友情链接 ┋  与我在线 ┋  汇款确认 ┋  管理 ┋  TOP
    Linux.Unix爱好者家园  http://www.unix-cd.com/
    联系我们:sdccf@163.com
    腾讯QQ: 7644599
    备案序号:鲁ICP备05000455号
    Copyright (c) 2001-2008 Unix-cd.com. All Rights Reserved.