- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我在比赛的某个地方发现了这个问题,但还没有想出解决方案。
The boy has apples and keeps in boxes. In one box no more than N/2. How many methods he can put candies to boxes.
所以我要做的是使用 DP 实现解决方案。这是我的代码:
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <unistd.h>
#include <vector>
#define size 1002
using namespace std;
long long a[size][size];
int n, k;
int main()
{
cin >> n >> k;
int kk = n/2;
for(int i = 0; i <= k; ++i)
a[0][i] = 1;
a[0][0] = 0;
for(int i = 0; i <= kk; ++i)
a[i][1] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = 2; j <= k; ++j) {
int index = 0;
long long res = 0;
while(1) {
res += a[i-index][j - 1];
index += 1;
if(index == kk + 1 || i-index < 0)
break;
}
a[i][j] = res;
}
}
cout << a[n][k] << endl;
}
但问题是我们有大量的输入,例如:
2 ≤ N ≤ 1000 is a quantity of the candies, N - even; 2 ≤ S ≤ 1000 - is a quantity of small boxes.
因此,对于 N = 1000 和 S = 1000 这样的输入,我必须花费 5*10^8 次操作。而且数字很大,所以我必须使用 BigInteger 算法?
也许有算法可以在线性时间内解决这个问题?谢谢,对不起我的英语!
最佳答案
您可以通过以下观察轻松地将时间复杂度从 O(kn^2) 降低到 O(nk):
for(int i = 1; i <= n; ++i) {
for(int j = 2; j <= k; ++j) {
int index = 0;
long long res = 0;
while(1) {
res += a[i-index][j - 1];
index += 1;
if(index == kk + 1 || i-index < 0)
break;
}
a[i][j] = res;
}
}
对于每个a[i][j]
,我们可以很容易地看到
a[i][j] = a[k][j - 1]
与 k 从 (i - n/2)
到 i
因此,如果我们创建一个数组 sum
来存储上一步所有索引的总和,我们可以从上面的嵌套循环中减少一个 for 循环
a[i][j] = sum[i] - sum[i - (n/2) - 1];
伪代码:
long long sum[n + 1];
for(int j = 2; j <= k; ++j) {
long long nxt[n + 1];
for(int i = 1; i <= n; ++i) {
int index = 0;
long long res = sum[i] - sum[i - (n/2) - 1];
a[i][j] = res;
nxt[i] = nxt[i - 1] + a[i][j];//Prepare the sum array for next step
}
sum = nxt;
}
注意:以上代码没有处理数组sum
的初始化步骤,也没有处理i < n/2的情况。这些情况应该很容易处理。
更新:
我的以下 Java 解决方案通过使用类似的想法被接受:
public static void main(String[] args) throws FileNotFoundException {
// PrintWriter out = new PrintWriter(new FileOutputStream(new File(
// "output.txt")));
PrintWriter out = new PrintWriter(System.out);
Scanner in = new Scanner();
int n = in.nextInt();
int s = in.nextInt();
BigInteger[][] dp = new BigInteger[n + 1][2];
BigInteger[][] count = new BigInteger[2][n + 1];
int cur = 1;
for (int i = 0; i <= n / 2; i++) {
dp[i][0] = BigInteger.ONE;
count[0][i] = (i > 0 ? count[0][i - 1] : BigInteger.ZERO)
.add(dp[i][0]);
}
for (int i = n / 2 + 1; i <= n; i++) {
dp[i][0] = BigInteger.ZERO;
count[0][i] = count[0][i - 1];
}
for (int i = 2; i <= s; i++) {
for (int j = 0; j <= n; j++) {
dp[j][cur] = dp[j][1 - cur].add((j > 0 ? count[1 - cur][j - 1]
: BigInteger.ZERO)
.subtract(j > n / 2 ? count[1 - cur][j - (n / 2) - 1]
: BigInteger.ZERO));
count[cur][j] = (j > 0 ? count[cur][j - 1] : BigInteger.ZERO)
.add(dp[j][cur]);
}
cur = 1 - cur;
}
out.println(dp[n][1 - cur]);
out.close();
}
关于c++ - 组合学 - 糖果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31742428/
我正在对一款流行游戏 (Minecraft) 进行一些修改,我在地形生成中看到了这些线条, double d4 = 1.0D; d4 *= d4; d4 *= d4; d4 = 1.0D - d4;
如何在没有浮点单元的处理器上执行 float 学运算?例如低端 8 位微 Controller 。 最佳答案 看看这篇文章:http://www.edwardrosten.com/code/fp_te
抱歉这个冗长的标题。我的代码针对没有浮点单元的微 Controller (msp430),但这应该适用于任何类似的 MCU。 如果我将一个大的运行时变量与通常被认为是浮点十进制数 (1.8) 相乘,M
我偶尔会在这个方法中遇到 stackoverflow 异常。 double norm_cdf(const double x) { double k = 1.0/(1.0 + 0.2316419
这是一个让我在过去几个小时里完全困惑的问题...... 我的程序中有一个硬编码的方程式: double s2; s2 = -(0*13)/84+6/42-0/84+24/12+(6*13)/42; 每
我知道 float 学充其量是丑陋的,但我想知道是否有人可以解释以下怪癖。在我测试的大多数编程语言中,将 0.4 添加到 0.2 会产生轻微错误,而 0.4 + 0.1 + 0.1 则不会。 两者计算
随着数据量持续增长,对合格数据专业人员的需求也会增长。具体而言,对SQL流利的专业人士的需求日益增长,而不仅仅是在初级层面。 因此,Stratascratch的创始人Nathan Rosidi以及我觉
当使用 c++ 或 -O0 编译时,以下 -O1 程序给出了数值不同的结果。 #include #include #include #include int main() { std::a
我正在尝试使用 SVG 在 map 上绘制飞行路径。我在 Leaflet 之上使用 d3,但所使用的框架不会对我的问题产生影响 - 这是三 Angular 关系。 http://fiddle.jshe
使用 IEEE754 float (在 JavaScript 中)时,与数学相关的精度损失风险是什么? 10*.1 即整数乘以有理数。 最佳答案 注意:该问题经过编辑,在发布此答案后很长时间添加了“t
我需要为网站 UI 做一些基本的 float 学运算(金钱的加法和乘法)。我知道 Javascript float 由于存储方式的原因并不准确,但我也知道以某种方式,可以获得我所需的准确度。我知道这一
我有一些像下面这样的宏: #define THING_LENGTH (512) #define MAX_COUNT (4096*8) #define MAX_LENGTH ((int32)((floa
我认为这是一个非常基本的问题 - 我正在执行此功能: private double convertMetersToFeet(double meters) { //function converts
我想在不损失太多精度的情况下替换这些函数中的 float 学,因为我没有 FPU。这可能吗?我认为逗号后的 3 个数字就足够了。 inline float smaller_f(float value,
我需要一个类来表示 double vector (在数学意义上)。 我需要的特殊功能: 任意维度 vector (我通常使用 10 - 100,000 维度) 高性能(用于受 CPU 限制的数字代码)
此社区 Wiki 问题的公认答案:What are best practices that you use when writing Objective-C and Cocoa?说 iPhone 不能
This question already has an answer here: Trouble with float on C [duplicate]
以下代码有问题: private const int movementMultiplier = 2; void Test() { XmlNode xnXCoordinate = xd.Sele
大家早上好 我在 float 学方面遇到了一些问题,完全迷失在“.to_f”、“*100”和“.0”中! 我希望有人能帮助我解决我的具体问题,并准确解释他们的解决方案为何有效,以便我下次理解这一点。
我的嵌入式 C 代码在具有单精度 FPU 的 Cortex M4F 上运行。我担心编译器多久将基于软件的 double 学放在诸如 ** float_var1 = 3.0 * int_var / fl
我是一名优秀的程序员,十分优秀!