F.Cut the Sequence(POJ 3017)
题意：给你一个长度为n的序列，要求把序列分割成若干个子串，每个子串的数字和不能大于m，每个子串的权值为子串的最大值，求所有子串的最小权值和
思路：dp[i] 维护从1 - i切割序列可以得到的最小权值和
又因为子串的的数字和不能超过m，可以得到转移方程是为 dp[i] = min(dp[k] + max(a[k + 1] , ... , a[i]) , dp[i])；同时k应该满足sum[i] - sum[k] <=m ；
a[k + 1] , ... , a[i] 之间的最大值可以采用单调队列来维护
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<cctype>
#include<stack>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-5;
ll arr[maxn];
ll sum[maxn];
ll dp[maxn];
struct node
{
ll pos;
ll maxx;
node(int x, int y)
{
pos = x;
maxx = y;
}
node() {}
}que[maxn];
int main()
{
ll n, m;
while (~scanf("%lld %lld", &n, &m))
{
sum[0] = 0;
dp[0] = 0;
for (int i = 1; i <= n; ++i) scanf("%lld", &arr[i]);
for (int i = 1; i <= n; ++i)
{
sum[i] = sum[i - 1] + arr[i];
dp[i] = sum[i];
}
int head = 1, rear = 1;
int l = 1;
for (ll i = 1; i <= n; ++i)
{
if (arr[i] > m)
{
printf("-1");
return 0;
}
while (rear > head&& arr[i] > que[rear - 1].maxx) rear--;
while (sum[i] - sum[l - 1] > m) ++l;
que[rear++] = node(i, arr[i]);
while (rear > head&& sum[i] - sum[que[head].pos - 1] > m) head++;
dp[i] = min(dp[i], dp[l - 1] + que[head].maxx);
for (int j = head + 1; j < rear; ++j)
{
dp[i] = min(dp[i], dp[que[j - 1].pos] + que[j].maxx);
}
}
printf("%lld
", dp[n]);
}
return 0;
}
E.Trade(HDU 3401)
题意：一个人要买股票，一个人每天可以买入ASi支股票，可以卖出BSi支股票，每支股票的买入价格为APi ，卖出价格为BPi，这个人最多可以持有MaxP支股票，询问T天之后，可以收获的最大利益是多少。一开始这个人持有0支股票，但是金钱无限，每隔W天可以进行一次买入或者卖出
思路：dp[i][j] 维护第i天持有j支股票的最大收益
dp[i][j] = max(dp[i - w - 1][k] + (j - k) * AP[i] , dp[i - w - 1][k] - (k - j) * AP[i] , dp[i - w - 1][j] );
转移方程表示在第i天买入股票，卖出股票，既不买入股票也不卖出股票三种情况中去最小
以买入股票为例，卖出股票和买入股票同理
如果第i天买入了股票 dp[i][j] = dp[i - w - 1][k] + (j - k) * AP[i]； 因式分解dp[i][j] + j * AP[i] = dp[i - w - 1][k] + k * AP[i];
因此对于每个i用单调队列维护dp[i - w - 1][k] + k * AP[i]的最大值
同时要求每天买入的股票不超过AS[i]支股票
注：初始化的需要将数组元素初始化为-INF，因为炒股还有有可能会亏钱的，但是最后的结果肯定是大于等于0的，因为如果炒股亏钱的话，那就不要炒股啦。
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<cctype>
#include<stack>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 100;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-5;
int ap[maxn], bp[maxn], as[maxn], bs[maxn];
int dp[2020][2020];
struct node
{
int val;
int num;
node(int a, int b)
{
val = a;
num = b;
}
node(){}
}que[maxn];
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
memset(dp, -inf, sizeof dp);
int n, m,maxx;
scanf("%d %d %d", &n,&maxx,&m);
for (int i = 1; i <= n; ++i)
{
scanf("%d %d %d %d", &ap[i], &bp[i], &as[i], &bs[i]);
}
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= maxx; ++j)
dp[i][j] = -inf;
for (int i = 1; i <= m + 1; ++i)
for (int j = 0; j <= as[i]; ++j) dp[i][j] = (-ap[i] * j);
for (int i = 2; i <= n; ++i)
{
for(int j = 0 ; j <= maxx ; ++ j)
dp[i][j] = max(dp[i - 1][j], dp[i][j]);
if (i <= m + 1) continue;
// 买入 维护一个单调递减队列
int rear = 1, head = 1;
for (int j = 0; j <= maxx; ++j)
{
while (rear > head&& que[rear - 1].val < dp[i - m - 1][j] + j * ap[i]) rear--;
que[rear++] = node(dp[i - m - 1][j] + j * ap[i], j);
while (rear > head&& que[head].num + as[i] < j) head++;
dp[i][j] = max(dp[i][j], que[head].val - j * ap[i]);
}
rear = 1, head = 1;
for (int j = maxx; j >= 0; --j)
{
while (rear > head&& que[rear - 1].val < dp[i - m - 1][j] + j * bp[i]) rear--;
que[rear++] = node(dp[i - m - 1][j] + j * bp[i], j);
while (rear > head&& que[head].num - bs[i] > j) head++;
dp[i][j] = max(dp[i][j], que[head].val - j * bp[i]);
}
}
int ans = -inf;
for (int i = 0; i <= maxx; ++i)
{
ans = max(ans, dp[n][i]);
}
ans = ans < 0 ? 0 : ans;
cout << ans << endl;
}
return 0;
}