某山寨

z4zr的待调教小窝

POJ1953 World Cup Noise DP入门

POJ1953 World Cup Noise DP入门

POJ1953
一道很好的dp入门题目。。。被我坑了。
开始读题没有读明白误解了题目 因为它跟Hrbust1132水数一样。。
后来发现是自己错了。。。

题意:给出n 000,001,010,100,101
看着题目。。dp啊 没感觉。。
试了试以下几个情况:
1------2
2------3
3------5
4------8
5------13
坑啊。。。。感觉怎么这么像斐波那契。。。。。。
果断f[n]=f[n-1]+f[n-2]...

//388K  16MS  292B
#include<stdio.h>
long long f[47]={0,2,3};
int main(){
    int i,T,n;
    for(i=3;i<46;i++)f[i]=f[i-1]+f[i-2];
    scanf("%d",&T);
    for(i=1;i<=T;i++){
        if(i!=1)putchar('\n');
        scanf("%d",&n);
        printf("Scenario #%d:\n%lld\n",i,f[n]);
    }
    return 0;
}

对不住题目了。。。。
看了下其他人的blog 感觉就是递推的撒。。。。。强制的按照DP来一下。。。
dp[i][

//388K  0MS  385B
#include<stdio.h>
int dp[50][2];
int main(){
    int i,T,n;
    dp[1][0]=1;dp[1][1]=1;
    for(i=2;i<46;i++){
        dp[i][0]=dp[i-1][1]+dp[i-1][0];
        dp[i][1]=dp[i-1][0];
    }
    scanf("%d",&T);
    for(i=1;i<=T;i++){
        if(i!=1)putchar('\n');
        scanf("%d",&n);
        printf("Scenario #%d:\n%d\n",i,dp[n][0]+dp[n][1]);
    }
    return 0;
}

动态规划慢慢来。。。。没有人带的话 就慢慢的找感觉吧。。。。


Warning: file_get_contents(http://api.hitokoto.us/rand): failed to open stream: Connection timed out in /data/htdocs/z4zr.host.smartgslb.com/usr/themes/Wcat/functions.php on line 87

文章二维码