[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]) (0m; for(int i=1;i>A[i]>>B[i]; } for(int i=1;i