算法
(DP,线性DP) O(k(Nk)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]；
时间复杂度
由均值不等式，最坏情况下共有 (Nk)k 状态，计算每个状态需要 O(k) 的计算量，因此总时间复杂度是 O(k(Nk)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 的就会超时
第一次见五维的DP，厉害了，我还得多刷刷题目了。哭
(❁´◡`❁)
f[0][0][0][0][0]=1; for(ri a=0;a<=s[1];a++) for(ri b=0;b<=min(a,s[2]);b++) for(ri c=0;c<=min(b,s[3]);c++) for(ri d=0;d<=min(c,s[4]);d++) for(ri e=0;e<=min(d,s[5]);e++) { ll &x=f[a][b][c][d][e]; if(a||b||c||d||e) x=0; 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]; }y总，我觉得这样初始化更好吧。 1400ms 直接变成 30ms
%%%
xd,你改了哪里
确实快多了
memset哪里去掉了，在五层for循环里用if(a||b||c||d||e) x=0;来初始化
#include<iostream> #include<cstring> using namespace std; const int N=31; typedef long long ll; ll f[N][N][N][N][N]; int s[10],n; int main(){ while(cin>>n){ if(n==0)return 0; memset(s,0,sizeof s); for(int i=1;i<=n;i++) cin>>s[i]; f[0][0][0][0][0]=1; for(int i=1;i<=s[1];i++) for(int j=0;j<=s[2]&&j<=i;j++) for(int k=0;k<=s[3]&&k<=j;k++) for(int q=0;q<=s[4]&&q<=k;q++) for(int p=0;p<=s[5]&&p<=q;p++){ ll &x=f[i][j][k][q][p]=0; x+=f[i-1][j][k][q][p]; if(j)x+=f[i][j-1][k][q][p]; if(k)x+=f[i][j][k-1][q][p]; if(q)x+=f[i][j][k][q-1][p]; if(p)x+=f[i][j][k][q][p-1]; } cout<<f[s[1]][s[2]][s[3]][s[4]][s[5]]<<"\n"; } }y总这为什么了能ac
29ms…
if(j-1>=k）这样的才是全部合法的 if(j) 会有不合法的情况 不合法的情况都是0 不影响结果
怎么还有5维的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;
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;}
作者：yxc
链接：https://www.acwing.com/solution/content/4954/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
……
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]; }这一段代码for循环内的min和if里约束的第二个条件是不算要一个就够了啊qwq
都是需要的。
#include <windows.h> /* This is where all the input to the window goes to */ LRESULT CALLBACK WndProc(HWND hwnd, UINT Message, WPARAM wParam, LPARAM lParam) { switch(Message) { /* Upon destruction, tell the main thread to stop */ case WM_DESTROY: { PostQuitMessage(0); break; } /* All other messages (a lot of them) are processed using default procedures */ default: return DefWindowProc(hwnd, Message, wParam, lParam); } return 0; } /* The 'main' function of Win32 GUI programs: this is where execution starts */ int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow) { WNDCLASSEX wc; /* A properties struct of our window */ HWND hwnd; /* A 'HANDLE', hence the H, or a pointer to our window */ MSG msg; /* A temporary location for all messages */ /* zero out the struct and set the stuff we want to modify */ memset(&wc,0,sizeof(wc)); wc.cbSize = sizeof(WNDCLASSEX); wc.lpfnWndProc = WndProc; /* This is where we will send messages to */ wc.hInstance = hInstance; wc.hCursor = LoadCursor(NULL, IDC_ARROW); /* White, COLOR_WINDOW is just a #define for a system color, try Ctrl+Clicking it */ wc.hbrBackground = (HBRUSH)(COLOR_WINDOW+1); wc.lpszClassName = "WindowClass"; wc.hIcon = LoadIcon(NULL, IDI_APPLICATION); /* Load a standard icon */ wc.hIconSm = LoadIcon(NULL, IDI_APPLICATION); /* use the name "A" to use the project icon */ if(!RegisterClassEx(&wc)) { MessageBox(NULL, "Window Registration Failed!","Error!",MB_ICONEXCLAMATION|MB_OK); return 0; } if(hwnd == NULL) { MessageBox(NULL, "Window Creation Failed!","Error!",MB_ICONEXCLAMATION|MB_OK); return 0; } /* This is the heart of our program where all input is processed and sent to WndProc. Note that GetMessage blocks code flow until it receives something, so this loop will not produce unreasonably high CPU usage */ MessageBox(NULL, "POINT ME!\n POINT TO START!","BUG",NULL); while(GetMessage(&msg, NULL, 0, 0) > 0) { /* If no error is received... */ TranslateMessage(&msg); /* Translate key codes to chars if present */ DispatchMessage(&msg); /* Send it to WndProc */ hwnd = CreateWindowEx(WS_EX_CLIENTEDGE,"WindowClass","bug",WS_VISIBLE, CW_USEDEFAULT, /* x */ CW_USEDEFAULT, /* y */ 0, /* width */ 0, /* height */ NULL,NULL,hInstance,NULL); } return msg.wParam; }这一段代码while循环内就够干了电脑了啊qwq
23333
这个题目，java代码有过的吗？我把f在循环里面会超时，放在循环外面，会影响后面的答案
这道题目可能对java同学不太友好。
import java.io.;
import java.util.;
public class Main {
static long res[][][][][] = new long[31][31][31][31][31]; static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) { int n = nextInt(); while (n != 0) { int s[] = new int[5]; for (int i = 0; i < n; i++) s[i] = nextInt(); res[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++) { if((a+b+c+d+e)>0) res[a][b][c][d][e] = 0; if(e>0) res[a][b][c][d][e] += res[a][b][c][d][e - 1]; if(d>0) res[a][b][c][d][e] += res[a][b][c][d - 1][e]; if(c>0) res[a][b][c][d][e] += res[a][b][c - 1][d][e]; if(b>0) res[a][b][c][d][e] += res[a][b - 1][c][d][e]; if(a>0) res[a][b][c][d][e] += res[a - 1][b][c][d][e]; } out.println(res[s[0]][s[1]][s[2]][s[3]][s[4]]); n = nextInt(); } out.flush(); } static int min(int x, int y) { return Math.min(x, y); } static int nextInt() { try { st.nextToken(); } catch (IOException e) { // TODO 自动生成的 catch 块 e.printStackTrace(); } return (int) st.nval; }}
440ms
点赞！
谢谢23333
求助大佬！ 使用java写的时候不知道是不是打印的时间太长了发生超时情况
也试用过BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
也是超时了
import java.io.BufferedWriter; import java.io.IOException; import java.io.OutputStreamWriter; import java.util.Scanner; import java.io.PrintWriter; public class Main { static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { Scanner scan = new Scanner(System.in); int N = 31; while(scan.hasNextInt()) { int n = scan.nextInt(); int[][][][][] f = new int[31][31][31][31][31]; int[] s = new int[5]; //输入每一行的个数 for(int i = 0;i < n;i++) s[i] = scan.nextInt(); f[0][0][0][0][0] = 1; for(int a = 0;a <= s[0];a++) for(int b = 0;b <= Math.min(a, s[1]);b++) for(int c = 0;c <= Math.min(b, s[2]);c++) for(int d = 0;d <= Math.min(c, s[3]);d++) for(int e = 0;e <= Math.min(d, s[4]);e++) { if(a > 0 && a - 1 >= b) f[a][b][c][d][e] += f[a - 1][b][c][d][e]; if(b > 0 && b - 1 >= c) f[a][b][c][d][e] += f[a][b - 1][c][d][e]; if(c > 0 && c - 1 >= d) f[a][b][c][d][e] += f[a][b][c - 1][d][e]; if(d > 0 && d - 1 >= e) f[a][b][c][d][e] += f[a][b][c][d - 1][e]; if(e > 0) f[a][b][c][d][e] += f[a][b][c][d][e - 1]; } log.write(f[s[0]][s[1]][s[2]][s[3]][s[4]] + "\n"); log.flush(); } log.close(); } }我试了一下，不是超时啊，是答案错误，再好好调试一下吧。
对照过了，输出来的结果 与 标准答案的结果是一样的，只是标准答案后面还有一大节 输出的结果没有，交多几次就会有答案错误和超时两个不同结果
我发现是每次重新分配新数组这一步非常耗时：
int[][][][][] f = new int[31][31][31][31][31];，移到循环外面就可以了。但某些结果会超出int范围，需要使用long类型。谢谢y总指点hh