算法
(DP,线性DP) $O(k(\frac{N}{k})^k)$
核心性质:
从高到低依次安排每个同学的位置,那么在安排过程中,当前同学一定占据每排最靠左的连续若干个位置,且从后往前每排人数单调递减。否则一定不满足“每排从左到右身高递减,从后到前身高也递减”这个要求。
DP的核心思想是用集合来表示一类方案,然后从集合的维度来考虑状态之间的递推关系。
受上述性质启发,状态表示为:
f[a][b][c][d][e]
代表从后往前每排人数分别为a, b, c, d, e
的所有方案的集合, 其中a >= b >= c >= d >= e
;f[a][b][c][d][e]
的值是该集合中元素的数量;
状态计算对应集合的划分,令最后一个同学被安排在哪一排作为划分依据,可以将f[a][b][c][d][e]
划分成5个不重不漏的子集:
- 当
a > 0 && a - 1 >= b
时,最后一个同学可能被安排在第1排,方案数是f[a - 1][b][c][d][e]
; - 当
b > 0 && b - 1 >= c
时,最后一个同学可能被安排在第2排,方案数是f[a][b - 1][c][d][e]
; - 当
c > 0 && c - 1 >= d
时,最后一个同学可能被安排在第3排,方案数是f[a][b][c - 1][d][e]
; - 当
d > 0 && d - 1 >= e
时,最后一个同学可能被安排在第4排,方案数是f[a][b][c][d - 1][e]
; - 当
e > 0
时,最后一个同学可能被安排在第5排,方案数是f[a][b][c][d][e - 1]
;
时间复杂度
由均值不等式,最坏情况下共有 $(\frac{N}{k})^k$ 状态,计算每个状态需要 $O(k)$ 的计算量,因此总时间复杂度是 $O(k(\frac{N}{k})^k)$。
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 31;
int n;
LL f[N][N][N][N][N];
int main()
{
while (cin >> n, n)
{
int s[5] = {0};
for (int i = 0; i < n; i ++ ) cin >> s[i];
memset(f, 0, sizeof f);
f[0][0][0][0][0] = 1;
for (int a = 0; a <= s[0]; a ++ )
for (int b = 0; b <= min(a, s[1]); b ++ )
for (int c = 0; c <= min(b, s[2]); c ++ )
for (int d = 0; d <= min(c, s[3]); d ++ )
for (int e = 0; e <= min(d, s[4]); e ++ )
{
LL &x = f[a][b][c][d][e];
if (a && a - 1 >= b) x += f[a - 1][b][c][d][e];
if (b && b - 1 >= c) x += f[a][b - 1][c][d][e];
if (c && c - 1 >= d) x += f[a][b][c - 1][d][e];
if (d && d - 1 >= e) x += f[a][b][c][d - 1][e];
if (e) x += f[a][b][c][d][e - 1];
}
cout << f[s[0]][s[1]][s[2]][s[3]][s[4]] << endl;
}
return 0;
}
其实不用memset f数组,两千多万的数组很浪费时间
每个状态只会被遍历一次,在for循环里把f[a][b][c][d][e]初始化为0就可以了
在for循环里不也是n ^ 5吗?
lz是说枚举状态的时候直接设为0,再转移
在赋值的时候也是要花时间的啊,本质上和memset一样,而且memset可能还会更快,因为CPU一直做重复的bit为0操作
memset是将整个数组清空,abcde是将使用过的数组空间清空,比如说出10000组 1\n1 的就会超时
y总,我觉得这样初始化更好吧。 1400ms 直接变成 30ms
%%%
xd,你改了哪里
确实快多了
memset哪里去掉了,在五层for循环里用if(a||b||c||d||e) x=0;来初始化
y总这为什么了能ac
29ms…
if(j-1>=k)这样的才是全部合法的 if(j) 会有不合法的情况 不合法的情况都是0 不影响结果
第一次见五维的DP,厉害了,我还得多刷刷题目了。哭
炸裂
请问这样的排列不可以吗....也满足从左到右递减,每列从后到前递减吧
为啥一定后排人数大于等于前排呢
如果一个位置是空,身高就为0
不是的, 因为题目要求第一排人数大于第二排, 类推
看题目N1>N2>N3
#哈哈哈#
这道题没有用到排列顺序需要递减的那个条件吗
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
typedef long long LL;
const int N = 31;
int n;
LL f[N][N][N][N][N];
int main()
{
while (cin >> n, n)
{
int s[5] = {0};
for (int i = 0; i < n; i ++ ) cin >> s[i];
memset(f, 0, sizeof f);
f[0][0][0][0][0] = 1;
}
作者:yxc
链接:https://www.acwing.com/solution/content/4954/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
……
这一段代码for循环内的$min$和if里约束的第二个条件是不算要一个就够了啊qwq
都是需要的。
这一段代码while循环内就够干了电脑了啊qwq
23333
这个题目,java代码有过的吗?我把f在循环里面会超时,放在循环外面,会影响后面的答案
这道题目可能对java同学不太友好。
import java.io.;
import java.util.;
public class Main {
}
440ms
点赞!
谢谢23333
求助大佬! 使用java写的时候不知道是不是打印的时间太长了发生超时情况
也试用过BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
也是超时了
我试了一下,不是超时啊,是答案错误,再好好调试一下吧。
对照过了,输出来的结果 与 标准答案的结果是一样的,只是标准答案后面还有一大节 输出的结果没有,交多几次就会有答案错误和超时两个不同结果
我发现是每次重新分配新数组这一步非常耗时:
int[][][][][] f = new int[31][31][31][31][31];
,移到循环外面就可以了。但某些结果会超出int
范围,需要使用long
类型。谢谢y总指点hh