DP 免费馅饼 HDU1176

vjudge题面

一道基本的DP题，状态转移很好想，每一个状态的位置\(pos\)都只能由上一秒的\(pos-1, pos, pos+1\)三个位置转移而来（当然要判断边界情况），这种简单的转移就直接写代码写死就行了，不需要像其他DP，还需要一个循环来专门决策。另外，这种DP写法还有点技巧，即是从最后一秒向前倒着推的，最后答案直接就是dp[0][5]（注意不是dp[1][5]）的值，不需要再循环判断一次。

AC 62ms Code:

#include <cstdio>

#include <cstring>

#define MAX(A,B) ((A)>(B)?(A):(B))

using namespace std;

int dp[100005][15];

int n;

int main()

{

    while(scanf("%d", &n), n!=0){

        memset(dp, 0, sizeof(dp));

        int cnt=0;

        for(register int i=0;i<n;i++){

            int x,t;scanf("%d %d", &x, &t);

            ++dp[t][x]; //直接在dp[][]里面操作，节约了一个a[][]费用数组

            cnt=MAX(cnt, t);

        }

        for(register int i=cnt;i>=0;--i)

            for(register int j=0;j<=10;++j){

                if(j==0) //边界判断

                    dp[i][j]+=MAX(dp[i+1][j], dp[i+1][j+1]);

                else if(j==10)

                    dp[i][j]+=MAX(dp[i+1][j], dp[i+1][j-1]);

                else

                    dp[i][j]+=MAX(dp[i+1][j], MAX(dp[i+1][j-1], dp[i+1][j+1]));

            }

        printf("%d\n", dp[0][5]); //最终状态即dp[0][5]

    }

    return 0;

}

巴特西

DP 免费馅饼 HDU1176

DP 免费馅饼 HDU1176

最新文章

热门文章