答题卡 题解

答题卡

https://ac.nowcoder.com/acm/contest/5389/C


考点:dp+思维
刚开始写的时候读不懂题意,不太明白如何下手,看了样例的图片后有了一些灵感,发现好像对称,索性找了一下规律。
发现我们可以把这个问题分为两种情况,第一种就是选左上角的格子,这样的话第一行第一列都不能涂,就是有dp[n-1]种;
如果不选左上角的格子,第一行还可以选n-1个格子,必须一次选两个对称的,这样就剩了dp[i-2]种可以选;
递推式为dp[i] = dp[i-1]+(i-1)*dp[i-2];
import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
    public static void main(String args[])throws IOException
    {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int n = (int)in.nval;
        long dp[] = new long[1000000];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] =4 ;
        dp[4] = 10;
        long mod = 1000000007;
        for(int i=5;i<=n;i++)
            dp[i] = (dp[i-1]+(i-1)*dp[i-2])%mod;
        out.println(dp[n]%mod);
        out.flush();
    }
                  }


全部评论

相关推荐

06-26 22:20
门头沟学院 Java
码农索隆:让你把简历发给她,她说一些套话,然后让你加一个人,说这个人给你改简历,然后开始卖课
我的求职精神状态
点赞 评论 收藏
分享
那一天的Java_J...:他本来公司就是做这个的,不就是正常的游戏客户端和服务器开发,软硬件联动,有啥恶心不恶心的,提前告诉你就是怕你接受不了,接受不了就没必要再往后走流程浪费时间,虽然这公司是一坨。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务