爆炸的符卡洋洋洒洒（01背包）

题目链接

https://ac.nowcoder.com/acm/contest/23479/I

题面

思路

我们从这n种符卡中选择一些卡牌，然后每张卡牌花费 a i a_i ai​的魔力，达到 b i b_i bi​的威力，我们要组合出一个魔力花费为k的倍数并且威力最大的情况，那么对于每一张卡牌来说我们可以选也可以不选，那么很容易联想到01背包，不过注意的是这里的背包容量很大，所以我们做一个%k的操作即可，如果是k的倍数那么就是0，我们就能得到状态转移方程： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − a [ i ] ] + b [ i ] ) f[i][j] = max (f[i-1][j] , f[i-1][j-a[i]] + b[i]) f[i][j]=max(f[i−1][j],f[i−1][j−a[i]]+b[i]) f[i][j]表示从前i个数中选出魔力消耗对k取模后为j的最大威力，然后初始状态我们初始化为-INF因为每一个状态都取不到，然后f[0][0]=0表示一张都不取的威力是0（很重要） 然后还要注意一点： f [ i − 1 ] [ j − a [ i ] + b [ i ] ] f[i-1][j-a[i]+b[i]] f[i−1][j−a[i]+b[i]]这个操作我们需要处理一下，不然可能会越界 ( ( j − a [ i ] ) ((j - a[i]) % k + k) % k ((j−a[i])，最后我们看f[n][0]的值是否为0就好啦，如果为0表示不存在刚好取到k的倍数的情况，所以就输出-1，否则就输出该值 关键点看代码

代码

#include
using namespace std;
//----------------自定义部分----------------
#define ll long long
#define int long long
#define mod 1000000007
#define endl "\n"
#define PII pair
#define INF 0x3f3f3f3f

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 1e3+10;
//----------------自定义部分----------------
ll n,k,m,q,a[N],b[N];

ll f[N][N];//f[i][j]表示从前i个数中选出魔力消耗为j的最大威力
/*
f[i][j] = max (f[i-1][j] , f[i-1][j-a[i]] + b[i]); 分别对于不选和选的情况
 */

signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	cin>>n>>k;
	for(int i = 1;i >a[i]>>b[i];
	}
	memset(f,-0x3f,sizeof f);
	f[0][0] = 0;
	for(int i = 1;i