[NOIp2016模拟]山羊大赛[dp]

题目大意

一只山羊,跑s米,至少需要多少秒。
山羊有一定疲劳值,疲劳值上限为p。
山羊有三种前进方式。

慢速奔跑,疲劳值-1,前进1m。
中速奔跑,疲劳值+2,前进5m。
快速奔跑,疲劳值+5,前进10m。
疲劳值到达上限时,必须慢速奔跑10s。

题解

#include

#include

#include
using namespace std;
int s,n;
int i,j;
int f[2][101];
int main()
{
freopen(“goat.in”,”r”,stdin);
freopen(“goat.out”,”w”,stdout);
scanf(“%d%d”,&s,&n);
if (n==1)
{
cout<=5)//可以用三种方式跑
{
x=max(f[(i-1)&1][j+1]+1,f[(i-1)&1][j-2]+5);
x=max(x,f[(i-1)&1][j-5]+10);
}
else if (j>=2) //可以用两种方式跑
{
x=max(f[(i-1)&1][j+1]+1,f[(i-1)&1][j-2]+5);
}
else if (j==1) x=f[(i-1)&1][j+1]+1;
}
if (x>=s)//跑到了
{
cout<<i;
return 0;
}
else f[i&1][j]=x;
}
}
return 0;
}