60分#7#8#9#10MLE的dp要滚动数组优化
  • 板块P1455 搭配购买
  • 楼主Onsin
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/7 11:07
  • 上次更新2024/8/7 11:58:00
查看原帖
60分#7#8#9#10MLE的dp要滚动数组优化
1379562
Onsin楼主2024/8/7 11:07

错误版:

for( int i=1; i <= p; i++ ){
		for( int j=1; j <= w; j++ ){
			if( j-pri2[i] >= 0 )
				dp[i][j] = max( dp[i-1][j] , dp[i-1][j-pri2[i]]+wea2[i] );
			else
				dp[i][j] = dp[i-1][j];
		}
	}

优化版:

for( int i=1; i <= p; i++ ){
		for( int j=w; j >= 1; j-- ){
			if( j-pri2[i] >= 0 )
				dp[j] = max( dp[j] , dp[j-pri2[i]]+wea2[i] );
		}
	}

仅供参考

2024/8/7 11:07
加载中...