HZOJ 发愤涂墙 动态规划

标签：int 50 long 发愤 ans include 涂墙 HZOJ

题面：

解题思路：

 

找到递推规律：f[i]=f[i-1]+f[i-2]

代码：

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    long long n;
    cin>>n;
    long long f[50]={0,2,2};
    for(int i=3;i<=n;i++){
        f[i]=f[i-1]+f[i-2];
    }
    cout<<f[n]<<endl;
    return 0;
}

 

类比另一道题：

墙壁涂色

题面：

 

 

题目分析：
　　找出 ans[n] 与 ans[n−1] 和 ans[n−2] 的关系。

　　考虑第 1块和 n-1块颜色不一样的情况，现在第 n 块要和第n−1 和 1 都不一样，但是只有3 种颜色，所以n 只有一种颜色选择，这种情况方案数正好是 ans[n−1]。

　　考虑第 1 块和 n−1 块颜色一样的情况，第 n−2 块必然要和第n−1 块不同，同时也就和第 1 块不同，前面n−2 块方案数是 ans[n−2]，第 n 块要和第 1 块和第n−1 块不同，有 2 种选择，所以这种情况方案数是 2∗ans[n−2]。

上面 2 种情况加起来就是总方案数。

注意： ans[1]=0 ///仔细地想一想，墙的最边缘的两部分不能相同

　　　ans[2]=6 ///刚开始我写的是ans[2]=3,当时以为ab和ba是一回事，但事实是“不是一回事”。

　　　数组要用long long

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    long long n,ans[50]={0,0,6};
    cin>>n; 
    for(int i=3;i<=n;i++){
        ans[i]=ans[i-1]+ans[i-2]*2;
    }
    cout<<ans[n]<<endl;
    return 0;
} 

总结：动态规划最重要的就是要找到转换方程，有了转换方程，代码编写起来就比较容易。

 

标签：int,50,long,发愤,ans,include,涂墙,HZOJ
From： https://www.cnblogs.com/anaxiansen/p/17002743.html