有n组物品,每组物品有两种,一种a个,一种b个.定义合成方式为同种k个,或者同组k个.问最多合成多少次
做法
对于每一组,最多只有s(s<k)个第一种与k-s个第二种进行同组组合,其余都用在同种的合成方式上.考虑 dp[i][j]: 前i组物品第一种有j个多余的情况下,最多合成的次数.对于该状态,相应的第二种就有$\sum_i(a_i+b_i) - k*dp_{ij} - j = B$考虑转移: 枚举dp[i-1][j], 再枚举当前组的同组组合状态s个第一种,k-s个第二种, 则:max{$dp[i][(j+a_i-s)$%$k]$, $dp[i−1][j] + (j+a_i-s)/k + (B+b_i-(k-s))/k$}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 505;
const ll LINF = 1e18 + 12;
constexpr int mod = 1e9 + 7;
int n, k;
ll dp[N][N];
inline void cmax(ll &x, ll y) { if(x<y) x = y; }
int main()
{
scanf("%d%d", &n, &k);
ll pre = 0;
for(int i=0; i<=n; i++)
for(int j=0; j<k; j++)
dp[i][j] = -1;
dp[0][0] = 0;
for(int i=1; i<=n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
for(int j=0; j<k; j++)
{
if(dp[i-1][j]==-1) continue;
cmax(dp[i][(j+a)%k], dp[i-1][j] + (j+a)/k + (pre-dp[i-1][j]*k-j+b)/k);
for(int s=0; s<=k; s++)
{
if(s>a || k-s>b) continue;
cmax(dp[i][(j+a-s)%k], dp[i-1][j] + (j+a-s)/k + (pre-dp[i-1][j]*k-j+b-(k-s))/k + 1);
}
}
pre += a + b;
}
ll ans = 0;
for(int i=0; i<k; i++) cmax(ans, dp[n][i]);
printf("%lld\n", ans);
return 0;
}
|