P1504 积木城堡/01背包板子

代码：

#define _CRT_SECURE_NO_WARNINGS 
#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 long long ll;
using namespace std;
const int N = 1010;
ll dp[N*N];
ll w[N]; ll f[N*N];
int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int n; cin >> n;
	ll minnlength = LLONG_MAX;

	for (int ii = 1; ii <= n; ii++)
	{
		ll x; memset(f, 0, sizeof(f));
		ll minn = 0;
		ll xx = 0;
		while (1)
		{
			cin >> x;
			if (x == -1)break;
			minn += x;
			xx++; w[xx] = x;
		}
		w[0] = xx;
		f[0] = 1;
		minnlength = min(minn, minnlength);
        //01背包样板
		for (ll i = 1; i <= xx; i++)//序号：i从1开始
		{
			for (ll j = minnlength; j >= w[i]; j--)//j从后面的长度开始
			{
				if (!f[j] and f[j - w[i]])
				{
					f[j] = 1;
					dp[j]++;
				}
			}
		}
	}
	for (ll i = minnlength; i > 0; i--)
	{
		if (dp[i] == n)
		{
			cout << i; 
			return 0;
		}
	}
	cout << 0;
	return 0;
}

适用于求长度的叠加，我之前写的那个过于麻烦了。