C - Greetings!

题目链接

题目大意

给n种信，每种信wi,hi,pi 分别代表长、宽、数量。
让选择k种信封来装这些信，每个信封里装一个。
如果把w,h的信装到了x,y的信封里，那么造成的浪费为x * y - w * h;
问装完这些最小造成多少浪费
n，k <= 15

题解

dp数组：
dp[i][j] 表示用i种信封装集合为j的信造成的浪费最小是多少。
j怎么表示一个集合? 状压。
主要是想不到怎么表示dp数组。害~
想到这里就变得很简单了。
先预处理出每种集合的浪费数量s：

	for (int  i= 0; i < (1 << n); i ++ )
	{
   
		ll ww = 0;
		ll hh = 0;
		ll num = 0;
		ll temp = 0;
		for (int j = 1; j <= n; j ++ )
		{
   
			if(i & (1 << (j - 1)))
			{
   
				ww = max(ww,w[j]);
				hh = max(hh,h[j]);
				num += p[j];
				temp += w[j] * h[j] * p[j];
			}
		}
		s[i] = ww * hh * num - temp;
	}

状态转移：
枚举k，然后枚举表示的集合，再枚举集合的子集，（当前这个集合从子集转移过来，）然后对这些取最小值。

	dp[0][0] = 0;
	for (int  i= 1; i <= k; i ++ )
	{
   
		for (int j = 0; j < (1 << n); j ++ )
		{
   
			for (int k = j; k > 0; k = (k - 1) & j)
			{
   
				if(dp[i - 1][j - k] != -1)
				{
   
					if(dp[i][j] == -1)
						dp[i][j] = dp[i - 1][j - k] + s[k];
					else
						dp[i][j] = min(dp[i][j],dp[ i- 1][j - k] + s[k]);
					// printf("%d %lld\n",k,s[k]);
				}
			}
			// printf("%d %d %lld\n",i,j,dp[i][j]);
		}
	}
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <bitset>
#include <stdlib.h>
#include <time.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
ll gcd(ll a,ll b){
   return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
   ll ans  = 1;while(b){
   if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{
   bool operator()(const pii & a, const pii & b){
   return a.second > b.second;}};

const int inf = 0x3f3f3f3f;

const int maxn = 1e5+5;
const int M = 20;
ll w[M];
ll h[M];
ll p[M];
ll dp[M][maxn];
ll s[maxn];
int main()
{
   
	int n,k;
	scanf("%d%d",&n,&k);
	for (int i = 1; i <= n; i++ )
	{
   
		scanf("%lld%lld%d",&w[i],&h[i],&p[i]);
	}
	for (int  i= 0; i < (1 << n); i ++ )
	{
   
		ll ww = 0;
		ll hh = 0;
		ll num = 0;
		ll temp = 0;
		for (int j = 1; j <= n; j ++ )
		{
   
			if(i & (1 << (j - 1)))
			{
   
				ww = max(ww,w[j]);
				hh = max(hh,h[j]);
				num += p[j];
				temp += w[j] * h[j] * p[j];
			}
		}
		s[i] = ww * hh * num - temp;
	}
	for (int  i= 0; i <= n; i ++ )
	{
   
		for (int j = 0; j < (1 << n);  j++ )
			dp[i][j] = -1;
	}
	// printf("1\n");
	dp[0][0] = 0;
	for (int  i= 1; i <= k; i ++ )
	{
   
		for (int j = 0; j < (1 << n); j ++ )
		{
   
			for (int k = j; k > 0; k = (k - 1) & j)
			{
   
				if(dp[i - 1][j - k] != -1)
				{
   
					if(dp[i][j] == -1)
						dp[i][j] = dp[i - 1][j - k] + s[k];
					else
						dp[i][j] = min(dp[i][j],dp[ i- 1][j - k] + s[k]);
					// printf("%d %lld\n",k,s[k]);
				}
			}
			// printf("%d %d %lld\n",i,j,dp[i][j]);
		}
	}
	ll ans = -1;
	for (int  i= 1; i <= k; i ++ )
	{
   
		if(ans == -1)
			ans = dp[i][(1 << n) - 1];
		else
			ans = min(dp[i][(1 << n) - 1],ans);
	}
	printf("%lld\n",ans);
}