正题
题目链接:https://www.luogu.com.cnp/problem/P1768
题目大意
n
n
n个城池，有
s
s
s个玩家对于每个城池有一定的兵。对于所有玩家的每个城池都有派兵一个人数，要求派兵人数之和为
m
m
m。如果你的派兵数列每大于一个玩家派兵数量的两倍那么就可以获得该城池编号的价值。
解题思路
其实我们可以把每个城池分成
s
s
s个物品，然后分组背包即可。
时间复杂度
O
(
s
n
m
)
O(snm)
O(snm)
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std
;
const ll N
=110;
ll s
,n
,m
,a
[N
][N
],f
[N
][2*N
*N
];
int main()
{
scanf("%lld%lld%lld",&s
,&n
,&m
);
for(ll i
=1;i
<=s
;i
++){
for(ll j
=1;j
<=n
;j
++)
scanf("%lld",&a
[j
][i
]),a
[j
][i
]=a
[j
][i
]*2+1;
}
for(ll i
=1;i
<=n
;i
++)
sort(a
[i
]+1,a
[i
]+1+s
);
for(ll i
=1;i
<=n
;i
++){
for(ll j
=0;j
<=m
;j
++)
f
[i
][j
]=f
[i
-1][j
];
for(ll j
=1;j
<=s
&&a
[i
][j
]<=m
;j
++){
for(ll k
=a
[i
][j
];k
<=m
;k
++)
f
[i
][k
]=max(f
[i
-1][k
-a
[i
][j
]]+j
*i
,f
[i
][k
]);
}
}
printf("%lld",f
[n
][m
]);
}
