Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

另一种思路,复杂度有点高,但测出来是g++16ms,有闲心的同学可以看看

Posted by Idy002 at 2014-08-21 17:42:06 on Problem 1260 and last updated at 2014-08-21 17:52:26
时间复杂度:O(n*sum_of_a) 空间复杂度O(n*sum_of_a)(可以优化到O(sum_of_a)
dp[i][j]:将i~n都卖完并且多买j个最少需要多少钱
初始状态:
dp[n][j] = (an+j+10)*pn (0<=j<=sum_of_a-an)
状态转移:
dp[i][j] = min( 
         dp[i+1][j+ai],    //不买i类
         dp[i+1][0]+(ai+j+10)*pi,   //买i类
)( 1<=i<=n-1, 0<=j<=sum_of_a-a[i]-a[i+1]-a[i+2]-...-a[n] )
目标状态:
dp[1][0]

证明:
对于当前状态dp[i][j],不可能出现买一部分i又留一部分到后面买,因为如果后面买的那一类是j,
若pi>pj,则全部都到后面买比只在后面买一部分优
若pi<pj,则全部都到这买更优

语文可能比较差,如果看不懂上面的证明,自己想也可以很快出来。
代码:(空间复杂度已优化)
#include <cstdio>
#define Min(a,b) ((a)<(b)?(a):(b))

int n;
int cnt[101], prc[101], scnt;
int dp[100001];

void input() {
	scanf( "%d", &n );
	scnt = 0;
	for( int i=1; i<=n; i++ ) {
		scanf( "%d%d", cnt+i, prc+i );
		scnt += cnt[i];
	}
}
int work() {
	scnt -= cnt[n];
	for( int j=0; j<=scnt; j++ )
		dp[j] = (cnt[n]+10+j)*prc[n];
	for( int i=n-1; i>=1; i-- ) {
		scnt -= cnt[i];
		int dp0 = Min( dp[cnt[i]], dp[0]+(cnt[i]+10)*prc[i] );
		for( int j=1; j<=scnt; j++ ) 
			dp[j] = Min( dp[j+cnt[i]], dp[0]+cnt[i]+10+j)*prc[i] );
		dp[0] = dp0;
	}
	return dp[0];
}
int main() {
	int T;
	scanf( "%d", &T );
	while(T--) {
		input();
		printf( "%d\n", work() );
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator