http://www.lydsy.com/JudgeOnline/problem.php?id=1643

这题和完全背包十分相似,

但是不能用1维做。。。。。。。。原因貌似是不能确定块数(还是有0的面积?)?

我们设f[i][j]表示i块木板面积为j时的方案数

很容易得出

f[i][j]=sum{f[i-1][j-k*k]} k为边长

边界为f[0][0]=1

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << #x << " = " << x << endl
#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; } const int N=10005;
int f[5][N];
int n; int main() {
read(n);
f[0][0]=1;
for1(l, 1, 4)
for1(i, 1, n)
for(int j=0; j*j<=i; ++j)
f[l][i]+=f[l-1][i-j*j];
printf("%d", f[4][n]+f[3][n]+f[2][n]+f[1][n]);
return 0;
}

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

最新文章

  1. Android开发之Toast
  2. UML类图之类与类的关系
  3. 《LDAP服务器的配置与客户端的测试》RHEL6——第一篇 运维工程师必考
  4. java集合--java.util.ConcurrentModificationException异常
  5. java一切乱码的解释 以及源头【转】
  6. VS2012+SQL2008+ODBC编程,第一篇博客,写的不好忘各位大神指点一二~
  7. Java基础知识总结(二)
  8. ZA7783:MIPI转LVDS/MIPI转RGB888/RGB转LVDS
  9. 安装xampp出错,安装xampp出错,windows找不到-n ?
  10. Java获取某年某周的第一天
  11. 仿iphone快速导航悬浮球
  12. 作业二:Git的安装与使用
  13. 从零开始 CentOs 7 搭建论坛BBS Discuz_X3.2
  14. mint linux 18.3 遇到“已安装的 post-installation 脚本 返回了错误号 127 ”问题的解决
  15. php倒计时
  16. ORB feature(O for orientation)
  17. bootStrap中的ul导航2
  18. html5中页面拨打电话的方式
  19. python的datetime常用方法
  20. socket编程基础-字节序/IP/PORT转换/域名

热门文章

  1. vue computed 可以使用getter和setter
  2. MQTT---HiveMQ源代码具体解释(四)插件载入
  3. Python-类属性与对象属性之间的关系
  4. EMQ ---问题集
  5. C#:复选框操作类
  6. 转 Android Activity之间动画完整版详解
  7. pandas contact 之后,若要用到index列,要记得用reset_index去处理index
  8. AutoFac文档9(转载)
  9. [转]IIS6 伪静态 IIS文件类型映射配置方法 【图解】
  10. Facebook Oauth2.0 API调用方法