UVa 12405

UVa 12405

题目：给你一条直线的麦田里面有的是荒地，有很多乌鸦，现在要放稻草人赶走乌鸦，

            每个稻草人影响自己所在的格子和两旁的格子，问最少要多少个稻草人。

分析：dp，动态规划。

            状态：f（i）表示前i个麦田需要最少的稻草人数；

            方程：f（i）= f（i-1）       （s[i] == '#'）

                                     f（i-3）+1   （s[i] == '.'）

说明：注意初始状态有3个。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>using namespace std;char buf[105];
int  f[105];int main()
{int T,N;while (~scanf("%d",&T)) {for (int t = 1; t <= T; ++ t) {scanf("%d%s",&N,buf);f[0] = (buf[0]=='.'?1:0);f[1] = (buf[0]=='.'||buf[1]=='.'?1:0);f[2] = (buf[0]=='.'||buf[1]=='.'||buf[2]=='.'?1:0);for (int i = 3; i < N; ++ i)if (buf[i] == '#')f[i] = f[i-1];else f[i] = f[i-3]+1;printf("Case %d: %dn",t,f[N-1]);}}return 0;
}