CDOJ 1638 Easy Problem
Problem:http://www.acm.uestc.edu.cn/problem.php?pid=1638
ある階段の入り口に到達するための時間を二次元配列で表して、下の階から上の階にDPすればいいです.左の階段の入り口ごとに、もっと上の階に上がると、すべてのものを送って左に戻ったり、直接右に行ったりできます.
ある階段の入り口に到達するための時間を二次元配列で表して、下の階から上の階にDPすればいいです.左の階段の入り口ごとに、もっと上の階に上がると、すべてのものを送って左に戻ったり、直接右に行ったりできます.
#include
int dp[101][2];
char floo[101];
int end[101][2];
int main()
{
int T, n, m, top, tmp;
scanf("%d", &T);
for(int cases=1; cases<=T; ++cases)
{
scanf("%d%d", &n, &m);
for(int i=1; i<=n; ++i)
{
scanf("%s", floo);
end[i][0] = m-1;
end[i][1] = 0;
for(int j=1; j end[i][1])
end[i][1] = j;
if(j < end[i][0])
end[i][0] = j;
}
}
}
if(m < 3)
{
printf("Case #%d: %d
", cases, n-1);
continue;
}
for(top = n; top>=1; --top)
{
if(end[top][0] == m-1)
continue;
else break;
}
if(top == 0)
{
printf("Case #%d: %d
", cases, n-1);
continue;
}
dp[0][0] = dp[0][1] = -1;
for(int i=1; i<=top; ++i)
{
dp[i][0] = dp[i][1] = 0x0fffffff;
if(end[i][0] != m-1)
{
tmp = dp[i-1][0]+1+2*end[i][1];
if(tmp < dp[i][0])
dp[i][0] = tmp;
tmp = dp[i-1][0]+m;
if(tmp < dp[i][1])
dp[i][1] = tmp;
tmp = dp[i-1][1]+1+2*(m-1-end[i][0]);
if(tmp < dp[i][1])
dp[i][1] = tmp;
tmp = dp[i-1][1]+m;
if(tmp < dp[i][0])
dp[i][0] = tmp;
}
else
{
tmp = dp[i-1][0]+1;
if(tmp < dp[i][0])
dp[i][0] = tmp;
tmp = dp[i-1][0]+m;
if(tmp < dp[i][1])
dp[i][1] = tmp;
tmp = dp[i-1][1]+1;
if(tmp < dp[i][1])
dp[i][1] = tmp;
tmp = dp[i-1][1]+m;
if(tmp < dp[i][0])
dp[i][0] = tmp;
}
}
int ans = (dp[top][0]