谢岂梵1
(Eli_Clark若知)
1
题解部分
我们看到题面应该能想到dp和搜索两种做法。但是因为这一课名字叫动态规划 所以我选择dp （？）
接下来设计状态，题目要求我们让最后的装甲值最大，那么f数组中存储的值就是在条件下最大的装甲值，而题目中要求在n只怪中击败m只怪，我们可以参考背包问题的状态设计，f[i][j]表示在前i只怪中击杀j只怪后剩余最大装甲值。可以列出状态转移方程：
f[i][j]=f[i-1][j];//不杀这只怪
f[i][j]=f[i-1][j-1]-a[i]+b[i];//杀这只怪
初始状态，即不杀怪的情况，要将f[0][0]设为0，表示不杀怪时装甲值就是题目所给，不发生改变。
但是在dp中要注意装甲值不能降到0以下，即如果选择杀掉这只怪，f[i-1][j-1]不能小于a[i]，所以需要写一句特判。
而因为要求最大值，所以我们需要把数组初始化为极小值，又双叒叕因为这道题的a[i]和b[i]不会有负数，所以初始化为0就可以。
那么看完整代码
memset(f,0,sizeof(f));
f[0][0]=x;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
f[i][j]=f[i-1][j];
if(f[i-1][j-1]>a[i]&&j>=1)f[i][j]=max(f[i][j],f[i-1][j-1]-a[i]+b[i]);
}
}
11 个赞
胡沛旸
(星影长河)
10
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010;
ll n,m,x;
struct node{
ll a,b;
}s[N];
ll findr(ll q,ll fl,ll fr)
{
ll l=fl,r=fr;
while(l<r)
{
ll mid=l+r+1>>1;
if(s[mid].a>q)
{
r=mid-1;
}
else
{
l=mid;
}
}
if(s[l].a<q)
{
return l;
}
return -1;
}
bool cmp(node A,node B)
{
return A.a<B.a;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
cin>>n>>m>>x;
for(int i=1;i<=n;i++)
{
cin>>s[i].a;
}
for(int i=1;i<=n;i++)
{
cin>>s[i].b;
}
while(m--)
{
ll f=findr(x,1,n);
ll p=0,k=INT_MIN;
for(int i=1;i<=f;i++)
{
if(k<s[i].b-s[i].a)
{
k=s[i].b-s[i].a;
p=i;
}
}
x+=k;
s[p].a=INT_MAX;
s[p].b=0;
if(x<=0)
{
break;
}
sort(s+1,s+n+1,cmp);
n--;
}
if(x<=0)
{
cout<<-1;
}
else
{
cout<<x;
}
return 0;
}
为什么我模拟只有76分
4 个赞
