首页 > 代码库 > hdu--3905--dp
hdu--3905--dp
状态转移方程不难想 我没想到另外还要开个数组 记录上一次的最优状态 wtf
主要是另外还要开个temp数组 这样可以减少一层for循环.
dp[x,y]在前x分钟我睡觉花掉了y分钟的时间 ( x>=y )
dp[x,y] = dp[x-1,y-1]假如我在x这个时间点正在睡觉 那么我得到价值就是 x-1这个时间点是一样的 而且我的睡觉花掉的时间又相比 x-1这个时间点 增加了1分钟
//dp[x,y] = max( dp[x,y] , dp[x-L]+sum[x]-sum[x-L])在x这个时间点我在听课 这边需要遍历所有的 1-x-L
上面的方程注释掉 我觉得这写的有点误导人 虽然后面又写上了遍历范围
这样写 比较好
x>=L+y的前提下
dp[x,y] = max( dp[x,y] , dp[k][y] + sum[x]-sum[k] ) 1 <=k <= x-L
其实 你可以发现 dp[k][y] + sum[x]-sum[k] 在 1<=k<=x-L-1之前 这些不就是 上一层 dp[x-1,y]所得出的吗 我们只是多增加了一个 x 这个时间点
就是 dp[x-L][y] + sum[x]-sum[x-L]
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 int n , m , L; 7 const int size = 1010; 8 int point[size]; 9 int sum[size];10 int temp[size][size];11 int dp[size][size];12 13 void solve( )14 {15 for( int i = 1 ; i<=n ; i++ )16 {17 for( int j = 0 ; j<=m&&j<=i ; j++ )18 { 19 if( j>=1 )20 dp[i][j] = dp[i-1][j-1];21 if( i>=j+L )22 temp[i][j] = max( temp[i-1][j]+point[i] , dp[i-L][j]+sum[i]-sum[i-L] );23 if( i>=L )24 dp[i][j] = max( dp[i][j] , temp[i][j] );25 }26 }27 }28 29 int main()30 {31 cin.sync_with_stdio(false);32 while( cin >> n >> m >> L )33 {34 sum[0] = 0;35 memset( dp , 0 , sizeof(dp) );36 memset( temp , 0 , sizeof(temp) );37 for( int i = 1 ; i<=n ; i++ )38 {39 cin >> point[i];40 sum[i] = point[i] + sum[i-1];41 }42 solve( );43 cout << dp[n][m] << endl;44 }45 return 0;46 }
其实temp完全可以写成一维的就足够了 因为记录的只是上一层的最优状态 滚动数组的味道.
注意下 因为point肯定为正值 所以 睡觉时间肯定是m 连续听课是least L 所以我们可以连续听课时间的时间区间长度是 >=L 我觉得这点很重要 而不是恰好为L 我一开始理解错了
hdu--3905--dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。