Explanation report of the explosion

The explosion's runes and cards are full of explanation reports

label ： Dynamic programming

Topic link

source ： Cattle from

Their thinking ：

The obvious knapsack problem
But observe again a,b Data range of , I can't drive that big dp Array
This inspires us to optimize , Because the title requires magic, the total cost is k Multiple
We can spend magic power on every data k modulus
Use dp[][j] Save directly in After taking the mold, the sum of magic is j The greatest power of time
Then the dynamic transfer equation ：
dp[i][j] = max(dp[i-1][j],dp[i-1][((j-a)%k+k)%k]+b);
After doing this, I found that it is the same as the problem of nine people and nine doors in nine hours , It's a pity that I didn't do it during the game

Code implementation ：

#include <bits/stdc++.h>
using namespace std;
long long dp[1050][1050];

int main(){
	int n,k;
	cin>>n>>k;
	int a,b;
	memset(dp,-0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int i=1;i<=n;i++){
		cin>>a>>b;		
		for(int j=0;j<k;j++){
		dp[i][j] = max(dp[i-1][j],dp[i-1][((j-a)%k+k)%k]+b);	
		}
	}
	long long ans = dp[n][0];
	if(ans<=0) ans=-1;
    cout<<ans<<endl;
	return 0;
}