洛谷 P1854 花店橱窗布置 题解
Analysis
给定一个f*v的矩阵
要求从第一行走到第f行，每行取走一个数，
且该行所取的数必须必上一行所取的数的列数大 ， 求所能取走的最大值
注意每一行所取走的数字的列数必须大于等该行的行号
因为必须给前面的花留下足够的花瓶
同理每一行所能取的最大的花瓶号必须小于等于v-(f-该行行数)
由此我们便可以很容易的得出状态转移方程
dp[i][j]=max(dp[i-1][k])+d[i][j](k<j)dp[i][j]=max(dp[i−1][k])+d[i][j](k<j)
其中dp[i][j]dp[i][j]表示从第一行走到第i行并取走该行第j个数所能取得的最大值
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<stack>
6 #define int long long
7 #define maxn 100+10
8 #define INF 9223372036854775807
9 using namespace std;
10 inline int read()
11 {
12 int x=0;
13 bool f=1;
14 char c=getchar();
15 for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
16 for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
17 if(f) return x;
18 return 0-x;
19 }
20 inline void write(int x)
21 {
22 if(x<0){putchar('-');x=-x;}
23 if(x>9)write(x/10);
24 putchar(x%10+'0');
25 }
26 int f,v;
27 int map[maxn][maxn];
28 int dp[maxn][maxn];
29 int path[maxn][maxn];
30 stack<int> s;
31 inline void print(int num,int x)
32 {
33 if(num==0) return;
34 s.push(x);
35 print(num-1,path[num][x]);
36 }
37 signed main()
38 {
39 freopen("flower.in","r",stdin);
40 freopen("flower.out","w",stdout);
41 memset(dp,128,sizeof(dp));
42 f=read();v=read();
43 for(int i=1;i<=f;i++)
44 for(int j=1;j<=v;j++)
45 map[i][j]=read();
46 for(int i=1;i<=v;i++) dp[1][i]=map[1][i];
47 for(int i=2;i<=f;i++)
48 for(int j=i;j<=v-(f-i);j++)
49 for(int k=1;k<j;k++)
50 {
51 if(dp[i-1][k]+map[i][j]>dp[i][j])
52 {
53 dp[i][j]=dp[i-1][k]+map[i][j];
54 path[i][j]=k;
55 }
56 }
57 int ans=-INF,fnum=0;
58 for(int i=1;i<=v;i++)
59 if(dp[f][i]>ans)
60 {
61 ans=dp[f][i];
62 fnum=i;
63 }
64 write(ans);
65 printf("\n");
66 print(f,fnum);
67 while(!s.empty())
68 {
69 write(s.top());
70 printf(" ");
71 s.pop();
72 }
73 return 0;
74 }请各位大佬斧正