想去写dp 所以就写了dp 这道dp 写的有点失败了，因为我根本 无法实现状态转移，最后看了眼学长的博客。
求 n个灯分成m组 的最大照明度 毫无疑问的是 设 f[i][j] 表示前i 个灯分成j组能 得到的最大照明。
可是状态转移的时候 无法转移 纵使我想到了前缀和 但是 唯一缺漏之处是 发现一组的灯里还有不能用的。
这就很气了，我不知道当前枚举的灯哪个用哪个不用 ，好像写不下去了。
一组灯中 有不用的灯这不是让搜索么？况且 我还是在一个三重循环中搜索这肯定不行 。
学长是这样写的 先预处理出 g[i][j] 表示第i个灯到第j个灯的最大照明度。
对于这一个区间采用搜索寻找出最大的照明度 ，我是真的没想到这是一个01背包问题。
有容积有价值 为什么不01背包，还是太年轻。又是没想到。。。
朴素的处理是这样的
for(int i=1;i<=n;++i) for(int j=i;j<=n;++j) { int s=T*(j-i+1); memset(w,0,sizeof(w)); for(int k=i;k<=j;++k) for(int r=s;r>=a[k];r--) w[r]=max(w[r],w[r-a[k]]+z[k]); g[i][j]=w[s]; }
可是这是接近n^4的复杂度一定GG。
考虑 怎么搞 我不太会。。
其实可以这样 对于枚举出的每个i j 灯的个数和体积在增长。
那么 直接拿出 i~n的全部容量再对每个新出现的灯进行01背包即可 最后只取i~j的容量的价值即可复杂度接近n^3 能A 了。
//#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<iomanip> #include<cstring> #include<string> #include<cstdlib> #include<cmath> #include<algorithm> #include<cctype> #include<utility> #include<set> #include<bitset> #include<queue> #include<stack> #include<deque> #include<map> #include<vector> #include<ctime> #define INF 2147483646 #define ll long long #define R register using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getc();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getc();} return x*f; } inline void put(int x) { x<0?putchar(‘-‘),x=-x:0; int num=0;char ch[50]; while(x)ch[++num]=x%10+‘0‘,x/=10; num==0?putchar(‘0‘):0; while(num)putchar(ch[num--]); putchar(‘\n‘);return; } const int MAXN=200; int n,m,T,maxx; int a[MAXN],z[MAXN]; int f[MAXN][MAXN];//f[i][j]表示前i个电灯分成j组能得到的最大照明 int g[MAXN][MAXN];//g[i][j]表示第i个电灯到第j个电灯为一组的最大照明 int w[MAXN*50]; int main() { //freopen("1.in","r",stdin); n=read();m=read();T=read(); for(int i=1;i<=n;++i)a[i]=read(),z[i]=read(); for(int i=1;i<=n;++i) { int s=T*(n-i+1); memset(w,0,sizeof(w)); for(int j=i;j<=n;++j) { for(int r=s;r>=a[j];r--) w[r]=max(w[r],w[r-a[j]]+z[j]); g[i][j]=w[T*(j-i+1)]; } } for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) for(int k=j-1;k<i;++k) f[i][j]=max(f[i][j],f[k][j-1]+g[k+1][i]); put(f[n][m]); return 0; }
原文：https://www.cnblogs.com/chdy/p/10611035.html
