## sgu 116 原

m2012

f[0...N][0...物品数-1]  => 注意: 第一件物品的编号为0

``````#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, '+');

}

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]);

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;
}``````

### m2012

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

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

GentlemanQc
2016/11/09
633
3

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

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

Tiny熊

4
0
5.线程实现

Eappo_Geng

3
0