跳至正文

NOIp 2007 第三题 矩阵取数游戏

  题目困扰了我很久,后来才知道,该怎么解题。
  这题说是说矩阵取数,但是仔细看看能够知道,和矩阵没什么关系,只每行的最大值有关,因为每行之间的最大没有任何关系。那么就将矩阵取数转变成了对数组取数,对数组取数很容易看出来是DP,DP方程如下:f[i][j] = max( 2 map[i] + 2  f[i + 1][j], 2  map[j] + 2  f[i][j – 1] )。最初状态是f[i][i] = 2 map[i]。f[i][j]的是i~j之间的能够取的最大值。
  方程我还解释一下,比如第一个数据吧:

     2 3
     1 2 3
     3 4 2
  我只说明第一行,f[0][0] = 2, f[1][1] = 4, f[2][2] = 6, 然后f[0][1] = max( 2 map[0] + 2 f[1][1], 2 map[1] + 2 f[0][0] ) = 10,也就是说"1 2"这两个数据应该先取1再去二,然后f[1][2] = 14.f[0][2] = 82..
  就是这样的思路,其实思路我三天前就有了,但是因为数据太大,2^80以上,用long long 都装不下,那只能使用高精度了,但是实在很难下手啊NOIp 2007 第三题 矩阵取数游戏 - NeWorldMaker - My S-K-Y
  怎么办?没办法了,只好先用int来写,然后封装起来,再把int改成高精度,啥?这句话没看懂?
  意思就是说我先写了下面第一段代码,没用高精度,只得了40分,但是下面这个代码的框架封装的很好,然后直接将几个函数修改一下就能够使用高精度了:
#include <stdio.h>
#include <string.h>
/
 ===============对使用"数"类型的封装=============== /
typedef struct{
        int num;
}num;

void give(num a, int n)
{
        a->num = n;
}

void add(num a, num b)
{
        a->num += b->num;
}

void addnum(num a, int n)
{
        a->num += n;
}

void copy(num a, num b)
{
        a->num = b->num;
}

int compare(num a, num b)
{
        return a->num – b->num;
}

void output(num a)
{
        printf("%d\n", a->num);
}

/ ===============程序的实现=============== /

num f[80][80];
num ans;
num s1, s2;
int map[80];

void srch(int n)
{
        int i, k;
        num t;
        memset(f, 0sizeof(f));
        for(i = 0; i < n; i++){
                give(&f[i][i], map[i]);
                addnum(&f[i][i], map[i]);
        }
        for(k = 1; k < n; k++){
                for(i = 0; i < n – k; i++){
                        copy(&s1, &f[i + 1][i + k]);
                        addnum(&s1, map[i]);
                        copy(&s2, &f[i][i + k – 1]);
                        addnum(&s2, map[i + k]);
                        if(compare(&s1, &s2) < 0){
                                t = &s2;
                        }else{
                                t = &s1;
                        }
                        copy(&f[i][i + k], t);
                        add(&f[i][i + k], t);
                }
        }
}

int main(void)
{
        int m, n;
        int i, j;
        memset(&ans, 0sizeof(ans));
        scanf("%d%d", &n, &m);
        for(i = 0; i < n; i++){
                for(j = 0; j < m; j++){
                        scanf("%d", &map[j]);
                }
                srch(m);
                add(&ans, &f[0][m – 1]);
        }
        output(&ans);
        return 0;
}
  高精度的代码等下发上来。

#include <stdio.h>
#include <string.h>
#include <math.h>
/
 =====================高精度实现部分===================== /
#define max(a, b) ((a)>(b)?(a):(b))
#define TOTAL 40
const int used = 100000000;
#define bits ((int)log10(used))
typedef struct{
        int num[TOTAL];
        int len;
}num;

static void deal(num a)
//防止高精度的漏洞.
//如:used = 10000, give(a, 10000), give(a, 1), give(b, 10000), add(a, b)
//此时a为20001而不是10001 
{
        int i;
        for(i = a->len; i < TOTAL; i++){
                a->num[i] = 0;        
        }
}

void give(num a, int n)
{
        int i;
        for(i = 0; n; i++){
                a->num[i] = n % used;
                n /= used;
        }
        a->len = i;
        deal(a);
}

void add(num a, num b)
        //这里有个bug, a和b 不能相同
{
        int i;
        int len = max(a->len, b->len);
        int re = 0;
        
        for(i = 0; i < len; i++){
                a->num[i] += b->num[i] + re;
                re = a->num[i] / used;
                if(re > 0){
                        a->num[i] %= used;
                }
        }
        a->len = len;
        if(re > 0){
                a->len++;
                a->num[i] = re;
                //掉了 a->num[i] = re; 这一行
        }
}

void addnum(num a, int n)
{
        int i;
        int re = 0;
        for(i = 0; n; i++){
                a->num[i] += (n % used) + re;
                n /= used;
                re = a->num[i] / used;
                if(re > 0){
                        a->num[i] %= used;
                }
        }
        a->len = max(i, a->len);
        if(re > 0){
                a->num[i] += re;
                //写成了=re; 
                a->len = max(i + 1, a->len);
        }
}

void copy(num a, num b)
{
        memcpy(a, b, sizeof(num));
}

int compare(num a, num b)
{
        if(a->len != b->len){
                return a->len – b->len;
        }

        int i;
        for(i = a->len – 1; i >= 0; i–){
                                //是i–不是i++ 
                if(a->num[i] != b->num[i]){
                        return a->num[i] – b->num[i];
                }
        }
        return 0;
        return a->num – b->num;
}

void output(num a)
{
        int i;
        int len = a->len,
num = a->num;
        printf("%d", num[len – 1]);
        len–;
        for(i = len – 1; i >= 0; i–){
                printf("%.d", bits, num[i]);
        }
        printf("\n");
}

/ =====================主函数部分===================== /

num f[80][80];
num ans;
num s1, s2;
int map[80];

void srch(int n)
{
        int i, k;
        num
t;
        memset(f, 0sizeof(f));
        for(i = 0; i < n; i++){
                give(&f[i][i], 2 * map[i]);
        }
        for(k = 1; k < n; k++){
                for(i = 0; i < n – k; i++){
                        copy(&s1, &f[i + 1][i + k]);
                        addnum(&s1, map[i]);
                        copy(&s2, &f[i][i + k – 1]);
                        addnum(&s2, map[i + k]);

                        if(compare(&s1, &s2) < 0){
                                t = &s2;
                        }else{
                                t = &s1;
                        }
                        copy(&f[i][i + k], t);
                        add(&f[i][i + k], t);
                }
        }
}

int main(void)
{
        int m, n;
        int i, j;
        memset(&ans, 0sizeof(ans));
        scanf("%d%d", &n, &m);
        for(i = 0; i < n; i++){
                for(j = 0; j < m; j++){
                        scanf("%d", &map[j]);
                }
                srch(m);
                add(&ans, &f[0][m – 1]);
        }
        output(&ans);
        return 0;
}

发表评论

您的电子邮箱地址不会被公开。