[luogu] P1336 zuijia课题选择 线性dp

传送门 :

状态表示 : f [ i ] [ j ] f[i][j] f[i][j]前 i i i门课程,完成 j j j次

其中 w = A [ i ] ∗ p o w ( k , B [ i ] ) w = A[i]*pow(k,B[i]) w=A[i]∗pow(k,B[i])

状态计算 : f [ i ] [ j ] = m i n ( f [ i − 1 ] [ j − k ] + w , f [ i ] [ j ] ) ( 0 < = k < = j ) f[i][j] = min(f[i-1][j-k] + w , f[i][j]) (0<=k<=j) f[i][j]=min(f[i−1][j−k]+w,f[i][j])(0<=k<=j)

初始化 : f [ i ] [ j ] = f [ i − 1 ] [ j − k ] + w f[i][j] = f[i-1][j-k]+ w f[i][j]=f[i−1][j−k]+w

从而线性的推过去就行了

const int N  = 30, M = 210;
int f[N][M];
int A[M],B[M];
int n,m;

void solve()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>A[i]>>B[i];
	}
	
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			for(int k = 0 ;k<=j;k++){
				int t =  A[i]*pow(k,B[i]);
				
				if(f[i][j] ==0 || i == 1)
				f[i][j] = f[i-1][j-k] + t;
				else
				f[i][j] = min(f[i-1][j-k]+t,f[i][j]); 
			}
		}
	}
	
	cout<>t;while(t -- )
    solve();
    return 0;
}