首页 > 代码库 > 关灯问题 dp
关灯问题 dp
题意是一排路灯,每个路灯有耗电量,照明度,需要给这n个路灯按顺序分组,每组内的最大耗电量是电灯数乘t,可以选择关闭一些电灯,求最大的照明度;
这题思路很明显,预处理出一个g[i][j]表示i到j分为一组的最大照明度,f[i][j]表示前i个分为j组的最大照明度,f[i][j]=max(f[k-1][j-1]+f[k][i]);
朴素的预处理是这么搞的
1 int h[maxm*maxn]; 2 for(int i=1;i<=n;i++) 3 for(int j=i;j<=n;j++){ 4 memset(h,0,sizeof(h)); 5 int s=(j-i+1)*t; 6 for(int k=i;k<=j;k++) 7 for(int c=s;c>=0;c--){ 8 if(c<w[k])break; 9 h[c]=max(h[c],h[c-w[k]]+v[k]);10 }11 g[i][j]=g[j][i]=h[s];12 }
n^4,无法接受,观察了一下,发现h数组每次都这么清一遍太浪费了,要想想怎么从前面的h中获取信息,发现每次h中有i-j的最优信息,然后处理i-j+1的时候相当于又处理了一遍i-j,要找i-j+1的g值,可以考虑一下不清空h数组,直接从j+1向上搞,但是每次最大耗电量都不一样,直接可以设成i-n的最大耗电,然后每次处理完后,在1-当前最大耗电里找最大值就行了,省了一维,可以通过了;
修改代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<algorithm> 6 #include<iomanip> 7 #include<cstdlib> 8 using namespace std; 9 const int maxn=170,maxm=60;10 int n,m,t,w[maxn],v[maxn];11 int g[maxn][maxn],f[maxn][maxm];12 void init(){13 scanf("%d%d%d",&n,&m,&t);14 for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);15 int h[maxn*maxn];16 for(int i=1;i<=n;i++){17 memset(h,0,sizeof(h));18 int s=(n-i+1)*t;19 for(int j=i;j<=n;j++){20 int S=(j-i+1)*t;21 for(int c=s;c>=0;c--){22 if(c<w[j])break;23 h[c]=max(h[c],h[c-w[j]]+v[j]);24 }25 g[i][j]=g[j][i]=h[S];26 }27 }28 }29 void work(){30 for(int i=1;i<=n;i++)31 for(int k=1;k<=m&&k<=i;k++){32 for(int j=k;j<=i;j++){33 f[i][k]=max(f[i][k],f[j-1][k-1]+g[j][i]);34 }35 }36 cout<<f[n][m]<<endl;37 }38 int main(){39 init();40 work();41 }
关灯问题 dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。