ABC015 高橋君の苦悩

ABC015 高橋君の苦悩

問題概要

リンク参照

問題リンク

https://atcoder.jp/contests/abc015/tasks/abc015_4

考察

• dp[i][j][k]:=i番目まで見てj枚スクショを使っていて幅がkの時の最大値としてdpを書きます
• スクショが張れないケースは幅をオーバーしてしまう場合と既にK枚貼ってあるときになります．
• ナップザックと似た遷移になりました

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<climits>
#include<bitset>
#include<stack>


/******************************************************************************************/


int dp[52][52][10005];

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	
	int W, N, K;
	cin >> W >> N >> K;

	vector<int> A(N), B(N);
	for (int i = 0; i < N; i++)
	{
		cin >> A[i] >> B[i];
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = K; j >= 0; j--)
		{
			for (int k = W; k >= 0; k--)
			{
				if (k + A[i] > W || j + 1 > K) {
					//おけない
					dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
				}
				else
				{
					//置かない
					dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
					//置く
					dp[i + 1][j + 1][k + A[i]] = max(dp[i + 1][j + 1][k + A[i]], dp[i][j][k] + B[i]);
				}
			}
		}
	}

	int maxi = 0;
	for (int i = 0; i <= K; i++)
	{
		for (int j = 0; j <= W; j++)
		{
			maxi = max(maxi, dp[N][i][j]);
		}
	}
	cout << maxi << endl;



}