P1833 樱花

题目：
链接：https://www.luogu.com.cn/problem/P1833
知识点：二进制优化，完全背包
emm怎么说呢，还是被卡内存，所以自顶而下编程不好！还是用滚动数组好点
代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef unsigned long long ll;
using namespace std;

const int N = 1e5+10;

int t[N], c[N], p[N];
int dp[2][1010];

int main()
{
	int times;
	int n;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int te1, te2, ts1, ts2;
	char cc;
	 cin >> te1 >> cc >> te2 >> ts1 >> cc >> ts2 >>n;
	times = 60 * (ts1 - te1) + ts2 - te2;
	
	ll id = 1;
	//在线进制拆分
	for (int i = 1; i <= n; i++)
	{
		cin >> t[id] >> c[id] >> p[id];
		if (p[id] > 1)
		{
			int timesa = p[id];
			int oct = t[id];
			int occ = c[id];
			for (int y = 1; y <= timesa; y <<= 1)
			{
				t[id] = y * oct;
				c[id] = y * occ;
				p[id] = y;
				timesa -= y;
				id++;
			}
			if (timesa)
			{
				t[id] = timesa * oct;
				c[id] = timesa * occ;
				p[id] = timesa;
				id++;
			}
		}
		else if (p[id] == 0)
		{
			ll timesa = times;
			ll oct = t[id];
			ll occ = c[id];
			for (int y = 1; y <= timesa; y <<= 1)
			{
				t[id] = y * oct;
				c[id] = y * occ;
				p[id] = y;
				timesa -= y;
				id++;
			}
			if (timesa)
			{
				t[id] = timesa * oct;
				c[id] = timesa * occ;
				p[id] = timesa;
				id++;
			}
		}
		else id++;
	}
	id--;
	int now =0;
    //背包
	for (int i = 1; i <= id; i++)
	{
	    now=1-now;
		for (int j = 0; j <= times; j++)
			if (t[i] > j)dp[now][j] = dp[1-now][j];
			else dp[now][j] = max(dp[1-now][j], dp[1-now][j - t[i]] + c[i]);
	}
	cout << dp[now][times];
	return 0;
}