文档章节

sgu 116

m2012
 m2012
发布于 2012/05/01 15:25
字数 877
阅读 61
收藏 0
本来是一题很简单的背包题, 结果老是RTE, 看了别人的题解, 最后才搞定, dp题吐血啊....

首先,要搞出dp转移方程, 其次,要考虑,对于问题的所有输入, 是否都经过你编写的dp的那部分代码, 这个很关键, 因为你本来的意图是, 用dp来处理程序的输入, 最后输出结果, 如果出现了bug, 使得程序的输入并不经过你的dp代码, 那肯会出错的!

我的做法是, 先将比N小的super-prime找出来, 这里有个陷阱, 当 N = 1, 会导致物品数量为0, 这个时候, 由于我编写的dp里面,计算的状态是:
f[0...N][0...物品数-1]  => 注意: 第一件物品的编号为0
也就是说, 我的dp所计算的所有情况里并不允许 "物品数为0" 这种情况, 一旦物品数为0, 就会跳过这部分的代码
举例子来说就是, 当N=1的时候, 按照我的程序的逻辑, 最后答案应该就是输出 f[N][-1], 下标是-1啊, 所以RTE了

总之, 用dp的时候, 要认真考虑边界条件, 确保问题的解总是能对应于某个你预料中的合法状态, 因为只有合法的状态才是用正确的方法计算出来的, 所以结果才是正确的, 如果问题的解对应的状态不是合法的, 那么肯定就不对了。

调试的时候, 一定不要怕麻烦, 最简单的情况也要试一下, 因为bug的存在位置是超越人类想象的。RTE一般是边界条件没有考虑周全。

#include <cstdio>
#include <vector>
#include <cmath>
#include <cassert>
#include <algorithm>
using namespace std;

vector<int> primeList;
vector<char> isPrime;

const int NOT_A_PRIME = '\0';
const int IS_A_PRIME = '\1';

int selectPrime(int limit) {
    int k;
    int i;

    primeList.resize(0);
    isPrime.resize(limit + 2);
    for (i = 0; i < isPrime.size(); ++i) isPrime[i] = IS_A_PRIME;
    isPrime[0] = NOT_A_PRIME;
    isPrime[1] = NOT_A_PRIME;

    for (i = 2; i <= limit; ++i) {
        if (isPrime[i]) { primeList.push_back(i); }
        for (k = 0; k < primeList.size(); ++k) {
            int cur = primeList[k] * i;
            if (cur > limit) break;
            isPrime[cur] = NOT_A_PRIME;
            if (i % primeList[k] == 0) break;
        }

    }

}

//==============================================================================


template <class VVType, class T>
void make2DVector(VVType &a, int d, int f, const T &initValue) {
    int i, j;
    a.resize(d);
    for (i = 0; i < d; ++i) {
        a[i].resize(f);
        for (j = 0; j < f; ++j) a[i][j] = initValue;
    }
}

//==============================================================================


bool cmpInt(int x, int y) {
    return !(x < y);
}




int N;
vector<int> v;
vector< vector<int> > f;
vector< vector<char> > w;
vector<int> ansList;


void init() {
    int i;
    scanf("%d", &N);

    selectPrime(N + 20);

    v.resize(0);
    for (i = 0; i < primeList.size(); ++i) {
        if (primeList[i] > N) break;
        if (isPrime[i + 1] == IS_A_PRIME) {
            v.push_back( primeList[i] );
        }
    }


    make2DVector(f, N + 1, 2, -1);
    make2DVector(w, N + 1, v.size() + 1, '+');

}



void trackBackAns() {
    ansList.resize(0);
    int n = N;
    int i = v.size() - 1;
    // assert(0 <= v.size() - 1);
    // assert(i == v.size() - 1);
    // assert(0 <= i && i <= v.size() - 1);
    int k;
    // int step = 0;
    while (1) {
        if (n == 0) return;
        if (i == 0) {
            for (k = 0; k < n / v[0]; ++k) ansList.push_back(v[0]);
            return;
        } else if (w[n][i] == '0') {
             i = i - 1;
        } else if (w[n][i] == '1') {
            ansList.push_back(v[i]);
            n = n - v[i];
        } else {
            // assert(0);
        }
    }
}


void dp() {
    int n, i;

    int wh = 0;

    for (i = 0; i < v.size(); ++i) {
        wh = 1 - wh;
        for (n = 0; n <= N; ++n) {
            f[n][wh] = -1;
            if (n == 0) {
                f[n][wh] = 0;
                w[n][i] = '_';
                continue;
            }
            if (i == 0) {
                f[n][wh] = n % v[i] == 0 ? n / v[i] : -1;
                w[n][i] = '*';
                continue;
            }

            if (f[n][1 - wh] != -1) {
                f[n][wh] = f[n][1 - wh];
                w[n][i] = '0';
            }
            if ( (n - v[i] >= 0) && (f[n - v[i]][wh] != -1) && (f[n][wh] == -1 || 1 + f[n-v[i]][wh] < f[n][wh]) ) {
                f[n][wh] = 1 + f[n-v[i]][wh];
                w[n][i] = '1';
            }

        }


    }

    if (f[N][wh] == -1) { printf("0\n"); return; }
    printf("%d\n", f[N][wh]);

    trackBackAns();

    sort(ansList.begin(), ansList.end(), cmpInt);

    for (i = 0; i < ansList.size(); ++i) {
        printf("%d", ansList[i]);
        if (i != ansList.size() - 1) printf(" ");
    }
    printf("\n");
}



int main() {
    init();
    if (v.size() <= 0) { printf("0\n"); return 0; }

    dp();
    return 0;
}


© 著作权归作者所有

共有 人打赏支持
上一篇: sgu 133
下一篇: 常用自定义函数
m2012
粉丝 16
博文 129
码字总数 52548
作品 0
广州
程序员
私信 提问
网络流建模汇总结

因为网上Dinic模板大多不规范或者可以被卡,所以先贴出一份跑得比较快的Dinic模板(主要快在maxflow()里面,可以仔细体会)。 (以下题意请自行百度) 1.最优分配 poj1149 应该是很裸的题了。...

qq_35649707
2017/08/04
0
0
RocketMQ同步双写问题

@tantexian 你好,想跟你请教个问题: 您好,我阅读了您写的RocketMQ同步双写的文章,很有帮助。但是我自己操作验证时,发现一个问题。我的测试环境是116和118为主broker,brokerRole为SYNC_...

GentlemanQc
2016/11/09
633
3
监控zabbix自定义OID

1.写监控服务的脚本 [root@db02 ~]# cat mysqlstat.sh #!/bin/bash mysqlstat=`ps aux | grep mysql | wc -l` echo $mysqlstat [root@db02 ~]# ./mysqlstat.sh 3 [root@db02 ~]# snmpwalk -v......

余二五
2017/11/16
0
0
求教:linux上的一个小问题

ALSA内核在/dev/snd目录下提供给用户的控制接口、PCM接口等如何使用? crw-rw----+ 1 root audio 116, 7 2011-11-01 13:31 controlC0 crw-rw----+ 1 root audio 116, 6 2011-11-01 13:31 hw......

ChenQi
2011/12/07
362
0
RocketMQ同步双写问题

@tantexian 你好,想跟你请教个问题: 您好,我阅读了您写的RocketMQ同步双写的文章,很有帮助。但是我自己操作验证时,发现一个问题。我的测试环境是116和118为主broker,brokerRole为SYNC_...

GentlemanQ
2016/11/09
113
0

没有更多内容

加载失败,请刷新页面

加载更多

Java单例模式学习记录

在项目开发中经常能遇见的设计模式就是单例模式了,而实现的方式最常见的有两种:饿汉和饱汉(懒汉)。由于日常接触较多而研究的不够深入,导致面试的时候被询问到后有点没底,这里记录一下学习...

JerryLin123
昨天
1
0
VSCODE 无法调试

VSCODE 无法调试 可以运行 可能的原因: GCC 的参数忘了加 -g

shzwork
昨天
3
0
理解去中心化 稳定币 DAI

随着摩根大通推出JPM Coin 稳定币,可以预见稳定币将成为区块链落地的一大助推器。 坦白来讲,对于一个程序员的我来讲(不懂一点专业经济和金融),理解DAI的机制,真的有一点复杂。耐心看完...

Tiny熊
昨天
4
0
5.线程实现

用于线程实现的Python模块 Python线程有时称为轻量级进程,因为线程比进程占用的内存少得多。 线程允许一次执行多个任务。 在Python中,以下两个模块在一个程序中实现线程 - _thread 模块 th...

Eappo_Geng
昨天
3
0
ServiceLoader

创建一个接口文件在resources资源目录下创建META-INF/services文件夹在services文件夹中创建文件,以接口全名命名创建接口实现类 内容me.zzp.ar.d.PostgreSQLDialectme.zzp.ar.d.Hype...

Cobbage
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部