注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4301  

2012-07-31 10:10:05|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2012多校合练第二题,DP,把各种状态都考虑到,自然状态方程就好写了

f[i][j][0],表示前i列,分成j块,且第i块相连;f[i][j][1]表示第i块分开

/*
 * fudq.cpp
 *
 *  Created on: 2012-07-31
 *      Author: fudq
 */
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<iomanip>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
using namespace std;
int dp[1010][2010][2];
#define N 100000007

int main()
{
    int t,i,j;
    dp[1][1][0] = dp[1][2][1] = dp[2][1][0] = 1;
    //dp[2][3][0] = dp[2][4][1] = 1;
    for(i = 2; i <= 1000; i++)
    {
        dp[i][1][0] = 1;
        dp[i][1][1] = 0;
        for(j = 2; j <= 2*i; j++)
        {
            dp[i][j][0] = (dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j][0] + 2*dp[i-1][j][1])%N;
            dp[i][j][1] = (dp[i-1][j-2][0] + dp[i-1][j-2][1] + 2*(dp[i-1][j-1][0] + dp[i-1][j-1][1]) + dp[i-1][j][1])%N;
        }
    }
    scanf("%d", &t);
    while(t-- && scanf("%d%d", &i, &j))
        printf("%d\n", (dp[i][j][0]+dp[i][j][1])%N);
    return 0;
}

http://page.renren.com/601081183/note/861865911?ref=minifeed&sfet=2012&fin=7&ff_id=601081183&feed=page_blog&tagid=861865911&statID=page_601081183_2&level=1
  评论这张
 
阅读(133)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018