最近做題沒狀態(tài)，其實我覺得最大的問題就是沒自信，不敢寫，還是沒有勇氣，我發(fā)現(xiàn)這都是自己的性格，生活中的我也是這個樣子，應該在不斷成長！

題目大意：連續(xù)的n個點，每個點可以染紅色或者藍色，求連續(xù)染m個紅色的點的所有方案數(shù)。

思路：1、對于連續(xù)的第i個點，如果前面已經(jīng)出現(xiàn)了m個染紅色的點，那么對于i+1的話就為ans【i]*2;

? ? ? ? ? ? ?2、對于前面沒有出現(xiàn)的點，那么對于第i+1個點，那最后m個就必須出現(xiàn)的，即為a[i-m-1]個，然后減去已經(jīng)出現(xiàn)的ans【i-m-1】，即為結(jié)果！

/ // File Name: 3725.cpp // Author: wang // mail: // Created Time: 2013/9/19 9:04:35 / #include <cstdio> #include <cstdlib> #include <climits> #include <cstring> #include <cmath>#include <algorithm> #include<iostream> #include<queue> #include <map> using namespace std; typedef long long ll; #define INF (INT_MAX/10) #define SQR(x) ((x)*(x)) #define rep(i, n) for (int i=0; i<(n); ++i) #define repf(i, a, b) for (int i=(a); i<=(b); ++i) #define repd(i, a, b) for (int i=(a); i>=(b); --i) #define clr(ar,val) memset(ar, val, sizeof(ar)) #define N 100005 #define mod 1000000007 ll a[N]; ll p[N]; ll ans[N]; int n,m; int main() {a[0]=1;repf(i,1,100000)a[i]=a[i-1]*2%mod;while(scanf("%d%d",&n,&m)!=EOF){if(m>n){printf("0\n");continue;}memset(ans,0,sizeof(ans));ans[m]=1;repf(i,m+1,n){ans[i]=((ans[i-1]*2+a[i-m-1]-ans[i-m-1])%mod+mod)%mod;}// repf(i,1,n) cout<<ans[i]<<" "; cout<<endl;cout<<ans[n]<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的zoj 3725 Painting Storages dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。