题解
巧妙的背包问题
我可以用按顺序遍历城堡,顺便表示出遍历到当前城堡时用掉了多少兵力,这样是可以穷尽所有兵力派送情况的
同时把这个城堡里的敌方兵力升序排序,然后遍历,表示为了消灭所有兵力小于等于ta的敌人所加的分
code
#include<bits/stdc++.h>
using namespace std;
int enemy[105][105]={0};
int dp[100005]={0};
int main()
{
int PLAYERS,CASTLES,FORCES;
cin>>PLAYERS>>CASTLES>>FORCES;
for(int player=1;player<=PLAYERS;player++)
for(int castle=1;castle<=CASTLES;castle++) cin>>enemy[castle][player];//矩阵转置,以便排序
for(int castle=1;castle<=CASTLES;castle++) sort(enemy[castle]+1,enemy[castle]+1+PLAYERS);//每个城堡只要超过一定人数就会加一定分
for(int castle=1;castle<=CASTLES;castle++)
for(int troop=FORCES;troop>=0;troop--)//troop代表当前城堡时还剩下多少兵力
for(int player=1;player<=PLAYERS;player++)//不是特指哪个敌人,而是遍历敌人的兵力
if(troop>2*enemy[castle][player]) dp[troop]=max(dp[troop],dp[troop-2*enemy[castle][player]-1]+player*castle);//降维背包
else break;
cout<<dp[FORCES]<<endl;
return 0;
}
标签:BJOI2019,排兵,P5322,enemy,int,player,troop,castle,dp
From: https://www.cnblogs.com/pure4knowledge/p/18050653