1643: [Usaco2007 Oct]Bessie's Secret Pasture 贝茜的秘密草坪

1643: [Usaco2007 Oct]Bessie's Secret Pasture 贝茜的秘密草坪

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 268  Solved: 223

[Submit][Status]

Description

农夫约翰已经从他的牧场中取得了数不清块数的正方形草皮,草皮的边长总是整数(有时农夫约翰割草皮的刀法不合适,甚至切出了边长为0的正方形草皮),他已经把草皮放在了一个奶牛贝茜已经知道的地方。 贝茜总是希望把美味的草皮放到她的秘密庄园里,她决定从这些草皮中取出恰好4块搬到她的秘密庄园中,然后把它们分成1×1的小块,组成一个面积为N(1<=N<=10,000)个单位面积的部分。 贝茜对选出这样四块草皮的方法数很感兴趣,如果她得到了一个4个单位面积的部分,那么她可以有5中不同的方法选4块草皮:(1,1,1,1),(2,0,0,0),(0,2,0,0),(0,0,0,2).顺序是有效的:(4,3,2,1)和(1,2,3,4)是不同的方法。

Input

第一行:一个单独的整数N。

Output

单独的一行包含一个整数,表示贝茜选四块草皮的方案数。

Sample Input

4

Sample Output

5

HINT

Source

Silver

 题解:呵呵呵呵,一道水水的DP(phile:这次没逗比? HansBug:么么哒)。。。不多说啥了,转移方程很简单,代码也很清楚。。。

 1 var
 2    i,j,k,l,m,n:longint;
 3    a:array[0..4,0..20000] of longint;
 4 begin
 5      readln(n);
 6      fillchar(a,sizeof(a),0);
 7      for i:=0 to trunc(sqrt(n)) do
 8          a[1,i*i]:=1;
 9      for i:=2 to 4 do
10          for j:=0 to n do
11              for k:=0 to trunc(sqrt(j)) do
12                  a[i,j]:=a[i,j]+a[i-1,j-k*k];
13      writeln(a[4,n]);
14 
15 end.
16           

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ4269: 再见Xor(线性基)

给定N个数,你可以在这些数中任意选一些数出来,每个数可以选任意多次,试求出你能选出的数的异或和的最大值和严格次大值。

664
来自专栏HansBug's Lab

2301: [HAOI2011]Problem b

2301: [HAOI2011]Problem b Time Limit: 50 Sec  Memory Limit: 256 MB Submit: 1737...

2565
来自专栏草根专栏

Typescript 查缺补漏

Types Casting: let input = xxx as HTMLInputElement; let input = <HTMLElement>xxx...

2223
来自专栏小樱的经验随笔

BZOJ 3211: 花神游历各国【线段树区间开方问题】

3211: 花神游历各国 Time Limit: 5 Sec  Memory Limit: 128 MB Submit: 3514  Solved: 1306...

3195
来自专栏HansBug's Lab

1081: [SCOI2005]超级格雷码

1081: [SCOI2005]超级格雷码 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 301  Solv...

2596
来自专栏HansBug's Lab

1677: [Usaco2005 Jan]Sumsets 求和

1677: [Usaco2005 Jan]Sumsets 求和 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 6...

2988
来自专栏一个会写诗的程序员的博客

禅与 JavaScript 编程艺术, Zen and The Art of JavaScript Programming禅与 JavaScript 编程艺术

Zen and The Art of JavaScript Programming

1151
来自专栏算法channel

用Word排版伪代码out了,推荐这个工具

多少次你看到别人的的伪代码排版如此完美而惊艳,心中不免好奇,怎么设计的?今天,和大家一起学习一款流行的排版利器:CTeX

1.1K0
来自专栏函数式编程语言及工具

SDP(9):MongoDB-Scala - data access and modeling

    MongoDB是一种文件型数据库,对数据格式没有硬性要求,所以可以实现灵活多变的数据存储和读取。MongoDB又是一种分布式数据库,与传统关系数据库不同...

3894
来自专栏HansBug's Lab

3402: [Usaco2009 Open]Hide and Seek 捉迷藏

3402: [Usaco2009 Open]Hide and Seek 捉迷藏 Time Limit: 3 Sec  Memory Limit: 128 MB ...

3427

扫码关注云+社区

领取腾讯云代金券