个人觉得挺难的一道DP题
不会
没有思路
于是去找的正解
于是。。
#include <iostream> #include <cstring> #define Max 1000010 using namespace std; int N; int number [Max]; ][]; // dp[i][j][1 or 0] 表示是第i个妹子 在第j段 0表示不放 1表示放 inline int max (int a, int b) { return a > b ? a : b; } int main() { ios :: sync_with_stdio (false); cin >> N; ; i <= N; i++) cin >> number [i]; ; i <= N; i++) // 枚举每个妹子 ; j <= ; j++) // 枚举 每一段 { dp [i][j][] = max (dp [i - ][j][], dp[i - ][j][]); /* 表示的是 第i个妹子 在第 j段不放的价值 等与前一个妹子在第j段放 or 不放的价值取大 */ ) dp [i][j][] = max (dp [i - ][j - ][], dp [i - ][j - ][]) + number [i]; /* 第0段(即j = 0 ) 表示的是 割过几个 妹子的价值*/ /* 如果不是第0段 那个当前妹子放入第j段的价值就是 前一个妹子放或不放入第 j 段的价值取大 */ dp [i][j][] = max (dp [i][j][], dp [i - ][j][] + number [i]); /* 第i个妹子放在第j段 的价值为当前价值 与 前一个妹子不放在第j段 于是另开一段后新加上当前妹子的价值*/ } ][], dp [N][][]); cout << Answer; ; }