UVa11157 - Dynamic Frog(动态规划)

#include <cstdio>#include <cstring>#include <algorithm>#include <cstdlib>usingnamespacestd;
constintN=110;
intmemo[N][N];
structRock{
charkind;
intsize;
};
Rockrock[N];
intn, d;
boolinput();
intsolve();
intdp(inti, intj);
intmain()
{
#ifndef ONLINE_JUDGEfreopen("d:\\OJ\\uva_in.txt", "r", stdin);
#endif // ONLINE_JUDGEintt;
scanf("%d", &t);
for (inti=1; i<=t; i++) {
input();
intans=solve();
printf("Case %d: %d\n", i, ans);
    }
return0;
}
boolinput()
{
scanf("%d", &n);
rock[0].kind='B', rock[0].size=0;
rock[n+1].kind='B';
scanf("%d", &rock[n+1].size);
for (inti=1; i<=n; i++) {
scanf(" %c-%d", &rock[i].kind, &rock[i].size);
    }
returntrue;
}
intsolve()
{
memset(memo, 0xff, sizeof(memo));
returndp(0, 0);
}
intdp(inti, intj)
{
int&res=memo[i][j];
if (res!=-1) returnres;
res=1<<30;
if (i>n&&j>n) returnres=0;
if (i<=j) {
for (intt=i; t<=n+1; t++) {
if (t==j&&rock[t].kind!='B') continue;
res=min(res, max(rock[t].size-rock[i].size, dp(t, j)));
        }
    } else {
for (intt=j; t<=n+1; t++) {
if (t==i&&rock[t].kind!='B') continue;
res=min(res, max(rock[t].size-rock[j].size, dp(i, t)));
        }
    }
returnres;
}