yukicoder : No.798 コレクション

★3にしてはやさしめ。
https://yukicoder.me/problems/no/798

問題

N個の商品を１個ずつ買い揃えることを考える。
i番の商品をオープンからd日後に買うと、(A[i]+d*B[i])円かかる。
１日には１個しか商品を買うことができない。
ただし、オープンから奇数日後は、1個商品を買うと任意の商品がオマケとしてついてくる。

全部をそろえる最低金額はいくらか。

解法

• 買うならB[i]が大きいものを先に買った方が良い
• 実際お金を出すのは(N-N/3)個で良い

という２点に気付けば、先に商品をB[i]降順にソートしたのち、(N-N/3)個を選ぶdpになる。

int N;
pair<int,int> P[2020];
ll dp[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		P[i]={y,x};
	}
	sort(P,P+N);
	reverse(P,P+N);
	FOR(i,N+5) dp[i]=1LL<<60;
	dp[0]=0;
	FOR(i,N) {
		for(j=N;j>=0;j--) {
			dp[j+1]=min(dp[j+1],dp[j]+P[i].second+j*P[i].first);
		}
	}
	
	cout<<dp[N-N/3]<<endl;
	
}

まとめ

今回早解きになってそう。