一道很好的DP题
比较容易想到的是时间复杂度为O(N3)，空间复杂度为O(N2)的dp. dp[i][j]表示前i 分钟，在已经休息了j 分钟的情况下所能拿到的最大分数。于是就有:
dp[i][j]=Max{ Max{ dp[i-k1][j-k1] },
Max{ dp[i-k2][j] + sum[(i-k2)~(i)] } }
其中 k1<=i, k1<=j, k2>=L,i-k2>=j 转移就是O(n)的了，
但是考虑到数据范围，这样做势必会超时，因此需要将转移的代价降下来。
1. 首先考虑 Max{ dp[i-k1][j-k1] }，我们发现所有的dp[i-k1][j-k1]都满足(i-k1)-(j-k1)=i-j。所以我们只需要记录一个数组a，a[i-j]表示的清醒i-j 分钟的前提下，最多能拿到的分数，每次计算一个dp[i][j]都更新一个a[i-j]。于是这一步转移就是O(1)了。
2. 再考虑 Max{ dp[i-k2][j] + sum[(i-k2)~(i)] }，我们发现转移有个比较有用的性质，在计算dp[i][j]时，无非是要找到一个分界点x，使得dp[x][j] + sum[(x)~(i)]最大，并且这个分界点必须落在[j,i-L]上。那么在计算dp[i+1][j]的时候，我们要找的就是分界点y，使得dp[x][j] +sum[(x)~(i+1)]最大，并且这个分界点必须落在[j,i+1-L]上。如果y 落在了[j,i-L]上，那么由于分数都是正整数，所以y 必定等于x，否则x 就不会是之前的最优分界点了。如果不是在[j,i-L]上，那么y 只能等于i+1-L，于是在计算dp[i+1][j]时只要知道计算dp[i][j]时的最优分界点，然后和新加入的分界点i+1-L 比较下就可以了。于是这一步就是O(1)了。
至此，整个程序的时间复杂度就是O(N2)，然后考虑到程序的空间优化，可以将关于j 的循环放在外层，最后可以将空间复杂度降为O(N)
(这段分析是转载的)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int input[1009],sum[1009],dp[1009][1009],divide[1009][1009];
int main(){
int m,n,l,i,j,k;
sum[0]=0;
while(scanf("%d %d %d",&n,&m,&l)==3){
for(i=1;i<=n;i++){
scanf("%d",&input[i]);
sum[i]=input[i];
if(i!=1)
sum[i]+=sum[i-1];
}
memset(dp,0,sizeof(dp));
memset(divide,0,sizeof(divide));
for(i=0;i<=m;i++)
divide[i+l][i]=i;
for(i=1;i<=n;i++)
for(j=0;j<=m &&j<=i;j++){
if(j>=1)
dp[i][j]=dp[i-1][j-1];
else{
if(i>=l)
dp[i][j]=sum[i];
}
if(i<j+l)
continue;
if(!divide[i][j])
divide[i][j]=divide[i-1][j];
if(dp[i-l][j]+sum[i]-sum[i-l]>dp[divide[i][j]][j]+sum[i]-sum[divide[i][j]])
divide[i][j]=i-l;
if(dp[i][j]<dp[divide[i][j]][j]+sum[i]-sum[divide[i][j]])
dp[i][j]=dp[divide[i][j]][j]+sum[i]-sum[divide[i][j]];
}
printf("%d\n",dp[n][m]);
}
}这样写空间浪费很大
|
|
|
|
|
Accepted |
3905 |
203MS |
8124K |
951 B |
C |
#include <stdio.h>
#include <string.h>
#define N 1010
#define Max( a, b ) ( a > b ? a : b )
int dp[ N ];
int cmp[ N ], sum[ N ];
void init ( int n ) {
memset ( cmp, 0, sizeof ( cmp ) );
for ( int i = 1 ; i <=n ; ++i ) {
sum[ i ] += sum[ i - 1 ];
}
}
int solve ( int n, int m, int l ) {
init ( n );
for ( int j = 0 ; j <= m ; ++j ) {
int div = j;
for(int i=0;i<=j;i++)
dp[i]=0;
for ( int i = j + 1 ; i <= n ; ++i ) {
dp[ i ] =cmp[ i - j ];
if ( i - l < j ) continue;
if ( dp[ div ] + sum[i] - sum[div] < dp[ i - l ] + sum[i] - sum[ i - l] )
div = i - l;
dp[ i ] = Max ( dp[ i ], dp[ div ] + sum[i] - sum[div] );
cmp[ i - j ] = Max ( cmp[ i - j ], dp[ i ] );
}
}
return dp[ n ];
}
int main ( void ) {
int n, m, l;
while ( scanf ( "%d%d%d", &n, &m, &l ) != EOF ) {
for ( int i = 1 ; i <=n ; ++i ) {
scanf ( "%d", &sum[ i ] );
}
printf ( "%d\n", solve ( n, m, l ) );
}
return 0;
}改为滚动数组。
Accepted |
3905 |
62MS |
156K |
1137 B |
G++ |