当前位置：首页 > article >正文

[wzoi]Help Bubu

article 2025/1/2 21:31:59

题目描述:

Bubu的书架上乱成一团了！请帮助他一下吧！

他的书架上一共有n本书。我们定义混乱值是连续相同高度书本的段数。例如，如果输的高度是30,30,31,31,32，那么混乱值为3,30,32,32,31的混乱度也是3，但31,32,31,32,31的混乱度为5，这实在是太乱了。Bubu想尽可能的减少混乱度，但他有点累了，所以他决定最多取出k本书，在随意将它们放到书架上。你能帮助他吗？

输入格式:

最多会有20组测试数据。每组测试数据开头为两个整数n，k，表示总共有n本书，最多可以进行k次搬书操作。接下来一行有n个整数，表示每本书的高度，从左到右。每本书的高度是25到32间的整数。最后一组数据后有一行n=k=0。

输出格式:

对于每一组数据，输出Case标号和最终最小的混乱度。在每组数据后打印一个空行。

样例输入:

5 2 
25 25 32 32 25
5 1 
25 26 25 26 25
0 0

样例输出:

Case 1: 2

Case 2: 3

提示:

时间限制: 1000ms
空间限制: 256MB

系统90分：

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define rint register int
using namespace std;

int n, m, st, u, ans, x;
int a[101], f[2][101][256][9], g[256];

void se(int x)
{
	for(rint i = 0; i <= m; i++)
		for(rint j = 0; j < 256; j++)
			for(rint k = 0; k <= 8; k++)
				f[x][i][j][k] = inf;
}

int main()
{
	for(rint i = 0; i < 256; i++)
		for(rint j = 0; j < 8; j++)
			if(i & (1 << j)) g[i]++;
	while(scanf("%d%d", &n, &m) != EOF)
	{
		if(!n && !m) break;
		st = 0;
		for(rint i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			a[i] -= 25;
			st |= (1 << a[i]);
		}
		u = 0;
		se(u);
		f[u][0][0][8] = 0;
		for(int i = 0; i < n; i++)
		{
			int t = a[i + 1];
			u ^= 1;
			se(u);
			for(rint j = 0; j <= min(i, m); j++)
				for(rint k = 0; k < 256; k++)
					for(rint l = 0; l <= 8; l++)
					{
						int tmp = f[u ^ 1][j][k][l];
						if(tmp == inf) continue;
						f[u][j + 1][k][l] = min(f[u][j + 1][k][l], tmp);
						if(l != t) f[u][j][k | (1 << t)][t] = min(f[u][j][k | (1 << t)][t], tmp + 1);
						else f[u][j][k][t] = min(f[u][j][k][t], tmp);
					}
		}
		ans = inf;
		for(rint i = 0; i <= m; i++)
			for(rint j = 0; j < 256; j++)
				for(rint k = 0 ; k <= 8; k++)
				{
					if(f[u][i][j][k] == inf) continue;
					int t = st ^ j;
					if(f[u][i][j][k] + g[t] < ans) ans = f[u][i][j][k] + g[t];
				}
		printf("Case %d: %d\n\n", ++x, ans);
	}
	return 0;
}

优化100分：

太太太难了！！！！！！加个优化吧！！！（参考生姜666的CSDN吐槽一下！）

#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#define inf 0x3f3f3f3f
#define rint register int
using namespace std;

int n, m, st, u, ans, x;
int a[101], f[2][101][256][9], g[256];

void se(int x)
{
   for(rint i = 0; i <= m; i++)
       for(rint j = 0; j < 256; j++)
           for(rint k = 0; k <= 8; k++)
               f[x][i][j][k] = inf;
}

int main()
{
   for(rint i = 0; i < 256; i++)
       for(rint j = 0; j < 8; j++)
           if(i & (1 << j)) g[i]++;
   while(scanf("%d%d", &n, &m) != EOF)
   {
       if(!n && !m) break;
       st = 0;
       for(rint i = 1; i <= n; i++)
       {
           scanf("%d", &a[i]);
           a[i] -= 25;
           st |= (1 << a[i]);
       }
       u = 0;
       se(u);
       f[u][0][0][8] = 0;
       for(int i = 0; i < n; i++)
       {
           int t = a[i + 1];
           u ^= 1;
           se(u);
           for(rint j = 0; j <= min(i, m); j++)
               for(rint k = 0; k < 256; k++)
                   for(rint l = 0; l <= 8; l++)
                   {
                       int tmp = f[u ^ 1][j][k][l];
                       if(tmp == inf) continue;
                       f[u][j + 1][k][l] = min(f[u][j + 1][k][l], tmp);
                       if(l != t) f[u][j][k | (1 << t)][t] = min(f[u][j][k | (1 << t)][t], tmp + 1);
                       else f[u][j][k][t] = min(f[u][j][k][t], tmp);
                   }
       }
       ans = inf;
       for(rint i = 0; i <= m; i++)
           for(rint j = 0; j < 256; j++)
               for(rint k = 0 ; k <= 8; k++)
               {
                   if(f[u][i][j][k] == inf) continue;
                   int t = st ^ j;
                   if(f[u][i][j][k] + g[t] < ans) ans = f[u][i][j][k] + g[t];
               }
       printf("Case %d: %d\n\n", ++x, ans);
   }
   return 0;
}