soj2930

soj2930

soj2930积木城堡

.action?id=2930

大概意思是一个聪明的小男孩，用积木搭城堡送给漂亮的小妹妹们，但是怕她们为了更高的城堡打架，所以要求做的城堡都一样高。

但是，他搭积木的时候又忘了，所以只能临时修改，从最上面往下一个积木一个积木拆掉，保证所有城堡一样高，同时越高越好。

超时了，先留档吧。。。一会吃完饭再检查

#include<cstdio>
#include<cstring>
using namespace std;
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
#define INF 0x3f3f3f3f
int dp[10010];
int high[110];
int result[10010];
int main()
{int test;scanf("%d",&test);while(test--){int n;scanf("%d",&n);memset(dp,INF,sizeof(dp));dp[0] = 0;for(int i = 0; i < n; i++){int num,sum = 0;for(num = 0; num < 110; num++){int a; scanf("%d",&a);if(a == -1) break;high[num] = a;sum += high[num];}for(int k = sum; k > 0;k--){for(int j = 0; j < num; j++)for(int g = k; g >= high[j];g--)dp[g] = min(dp[g-high[j]]+high[j],dp[g]);if(dp[k] != INF)result[k] += 1;}}int k;int maxs = 0;for(k = 1;k < 10010; k++)if(result[k] == n)maxs = max(k,maxs);printf("%d\n",maxs);}return 0;
}

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

我吃饱回来啦。然后修改了一下：

#include<cstdio>
#include<cstring>
using namespace std;
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
#define INF 0x3f3f3f3f
int dp[10010];
int high[110][110];
int result[10010];
int num[110];  //每组个数
int main()
{int test;scanf("%d",&test);while(test--){int n;scanf("%d",&n);memset(result,0,sizeof(result));memset(high,0,sizeof(high));memset(num,0,sizeof(num));                         //这三行没有就会一直哇int summin = INF;for(int i = 0; i < n; i++){int sum = 0;int a; scanf("%d",&a);while(a != -1){high[i][num[i]] = a;                     //num[i]存放第i组积木的个数，牛逼，数组可以做一切sum += a;num[i]++;scanf("%d",&a);}summin = min(summin,sum);}for(int k = summin; k > 0;k--){for(int i = 0; i < n; i++){memset(dp,INF,sizeof(dp));dp[0] = 0;for(int j = 0; j < num[i]; j++)for(int g = k; g >= high[i][j]; g--)dp[g] = min(dp[g-high[i][j]]+high[i][j],dp[g]);if(dp[k] != INF)result[k] += 1;}}int maxs = 0;for(int k = 1;k <= summin; k++)if(result[k] == n)maxs = max(k,maxs);printf("%d\n",maxs);}return 0;
}

最初的问题就是超时嘛，所以通俗来讲，让循环少点就快点。所以改成下面的。

本题的思想就是，从最小的开始扔，这样每一组有那哪些高度和都记录下来，高度和若存在就result[i]++，如果这些城堡每个都有某个高度和H，那么就是result[H] = n，等于组数，则输出这个高度H就好啦。

至于计算有多少种高度和，就是背包问题了，上面给出公式，完全背包。

撒花~