首页 > 代码库 > 关灯问题

关灯问题

看lzx的题解才写出来,lzx太神辣

原题:

在四川省绵阳中学的毓才路上,新建了若干漂亮的路灯,这给同学们晚上的出行带来很大的方便。但是,问题随之出现了。
一天晚上,我们信息学竞赛班的 SFJ 同学正往校门外走,忽然眼前一片漆黑,于是直 接把眼镜都摔掉了,再也找不到。后来 SFJ 同学从学校管理处了解到昨晚路灯突然熄灭是 因为电路不堪重负,导致空气开关跳闸。
善于思考的 SFJ 同学考虑将路灯进行改建,以避免再次出现类似的问题。
SFJ 同学仔细了解每盏路灯的耗电量 a[i]与照明度 z[i],已知共有 N 盏电灯,并且每盏电灯都可能有不同的耗电量与照明度,现在的问题是要把这 N 盏电灯分为 M 组,新分出的每组灯的耗电量(即是该组所有打开电灯的耗电量之和)不能超过该组的电灯数目的 T倍,在满足这样的前提下使得照明度尽可能的大,最后算出 M 组的最大照明度的和。由于每组耗电量的限制,该组中的某些电灯可能不被使用,但是仍然应该算作该组灯的数目。特别注意的是电灯按顺序给出,只能把相邻的几盏灯分在一组。 由于计算较为复杂,SFJ 同学经过反复的计算仍然不能确定结果,现在就请你为他编写
一个程序来解决这个问题。

2<=N<=160,1<=M<=50,1<=T,a[i],z[i]<=50

 

n^4很容易想

现在关键是如何优化到n^3

首先先确定一下思路,思路不一样后面可能会不太好搞

背包求f[i][j]表示从i到j最优值,然后g[i][j]表示直到i分了j组最优值,g[i][j]=max{g[j-1][k-1]+f[j][i]}

(感觉这个思路对我不太友好啊,我不怎么习惯这种思路

然后呢其实求f[i][j]的背包是可以重复使用的,只要最后结算到f[i][j]的时候使用的是j的上限即可

这个就需要知道背包如果不限制必须装满的话f[容量]就是最大值,因为不必从0开始装(我在做这道题之前还真不知道……
似乎可以用有理有据的底层优化n^4卡过?

可以尝试一下

代码:

技术分享
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<vector>
 7 using namespace std;
 8 int rd(){int z=0,mk=1;  char ch=getchar();
 9     while(ch<0||ch>9){if(ch==-)mk=-1;  ch=getchar();}
10     while(ch>=0&&ch<=9){z=(z<<3)+(z<<1)+ch-0;  ch=getchar();}
11     return z*mk;
12 }
13 int n,m,c,a[210],b[210];
14 int f[8100],g[210][210],h[210][210];
15 int main(){//freopen("ddd.in","r",stdin);
16     cin>>n>>m>>c;
17     for(int i=1;i<=n;++i)  a[i]=rd(),b[i]=rd();
18     for(int i=1;i<=n;++i){
19         memset(f,0,sizeof(f));
20         int w=(n-i+1)*c;
21         for(int j=i;j<=n;++j){
22             for(int k=w;k>=a[j];--k)
23                 f[k]=max(f[k],f[k-a[j]]+b[j]);
24             g[i][j]=f[(j-i+1)*c];
25         }
26     }
27     for(int i=1;i<=n;++i)
28         for(int k=1;k<=m && k<=i;++k)
29             for(int j=k;j<=i;++j)
30                 h[i][k]=max(h[i][k],h[j-1][k-1]+g[j][i]);
31     cout<<h[n][m]<<endl;
32     return 0;
33 }
View Code

 

关灯问题