[NOIp2017复习]dp题整理

  • P2858 [USACO06FEB]奶牛零食Treats for the Cows[区间dp]
  • P2867 [USACO06NOV]大广场Big Square[dp]
  • P2851 [USACO06DEC]最少的硬币The Fewest Coins[dp]
  • P1879 [USACO06NOV]玉米田Corn Fields[状压dp]
  • P1005 [NOIp2007]矩阵取数游戏[dp,高精度]
  • P2513 [HAOI2009]逆序对数列[dp+前缀和]

其实目的是清理文章,顺便复习一下写过的dp

P2858 [USACO06FEB]奶牛零食Treats for the Cows[dp]

题目描述

FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he receives over a given period time.

The treats are interesting for many reasons:The treats are numbered 1..N and stored sequentially in single file in a long box that is open at both ends. On any day, FJ can retrieve one treat from either end of his stash of treats.Like fine wines and delicious cheeses, the treats improve with age and command greater prices.The treats are not uniform: some are better and have higher intrinsic value. Treat i has value v(i) (1 <= v(i) <= 1000).Cows pay more for treats that have aged longer: a cow will pay v(i)*a for a treat of age a.Given the values v(i) of each of the treats lined up in order of the index i in their box, what is the greatest value FJ can receive for them if he orders their sale optimally?
The first treat is sold on day 1 and has age a=1. Each subsequent day increases the age by 1.

约翰经常给产奶量高的奶牛发特殊津贴,于是很快奶牛们拥有了大笔不知该怎么花的钱.为此,约翰购置了 N($1≤N≤2000$) 份美味的零食来卖给奶牛们.每天约翰售出一份零食.当然约翰希望这些零食全部售出后能得到最大的收益.这些零食有以下这些有趣的特性:

  • 零食按照1..N编号,它们被排成一列放在一个很长的盒子里.盒子的两端都有开口,约翰每天可以从盒子的任一端取出最外面的一个.
  • 与美酒与好吃的奶酪相似,这些零食储存得越久就越好吃.当然,这样约翰就可以把它们卖出更高的价钱.
  • 每份零食的初始价值不一定相同.约翰进货时,第i份零食的初始价值为Vi(1≤Vi≤1000).
  • 第i份零食如果在被买进后的第a天出售,则它的售价是vi×a.

$V_i$ 的是从盒子顶端往下的第i份零食的初始价值.约翰告诉了你所有零食的初始价值,并希望你能帮他计算一下,在这些零食全被卖出后,他最多能得到多少钱.

输入输出格式

输入格式:

Line 1: A single integer, N

Lines 2..N+1: Line i+1 contains the value of treat $V_i$

输出格式:

Line 1: The maximum revenue FJ can achieve by selling the treats

输入输出样例

输入样例#1:

5
1
3
1
5
2

输出样例#1:

43

说明

Explanation of the sample:
Five treats. On the first day FJ can sell either treat #1 (value 1) or treat #5 (value 2).
FJ sells the treats (values 1, 3, 1, 5, 2) in the following order of indices: 1, 5, 2, 3, 4, making 1x1 + 2x2 + 3x3 + 4x1 + 5x5 = 43.

题解

本来用 $f[i][j]$ 表示当 $0$~$i,j+1~n$被取完时,能得到的最多的钱
然后发现无法预处理
$f[i][j]$ 表示取 $i~j$ 段能够得到最多的钱
初始化
$f[i][i]=n*a[i]$;
也就是 $a[i]$ 放最后一个取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,maxx;
int f[2010][2010];
int a[2010];
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i][i]=a[i]*n;
}
for (int i=n;i>=1;i--)
for (int j=i;j<=n;j++)
f[i][j]=max(f[i+1][j]+a[i]*(n+i-j),f[i][j-1]+a[j]*(n+i-j));//分为取左端和右端两种情况
printf("%d",f[1][n]);
return 0;
}

P2851 [USACO06DEC]最少的硬币The Fewest Coins[dp]

题目描述

Farmer John has gone to town to buy some farm supplies. Being a very efficient man, he always pays for his goods in such a way that the smallest number of coins changes hands, i.e., the number of coins he uses to pay plus the number of coins he receives in change is minimized. Help him to determine what this minimum number is.
FJ wants to buy T ($1 ≤ T ≤ 10,000$) cents of supplies. The currency system has N (1 ≤ N ≤ 100) different coins, with values V1, V2, …, VN (1 ≤ Vi ≤ 120). Farmer John is carrying C1 coins of value V1, C2 coins of value V2, …., and CN coins of value VN (0 ≤ Ci ≤ 10,000). The shopkeeper has an unlimited supply of all the coins, and always makes change in the most efficient manner (although Farmer John must be sure to pay in a way that makes it possible to make the correct change).
农夫John想到镇上买些补给。为了高效地完成任务,他想使硬币的转手次数最少。即使他交付的硬 币数与找零得到的的硬币数最少。 John想要买价值为T的$(1<=T<=10000)$东西。有$N$$(1<=n<=100)$种货币参与流通,面值分别为V1,V2..Vn $(1<=V_i<=120)$。John有Ci个面值为Vi的硬币$(0<=Ci<=10000)$。我们假设店主有无限多的硬币, 并总按最优方案找零。

输入输出格式

输入格式:

Line 1: Two space-separated integers: N and T.
Line 2: N space-separated integers, respectively V1, V2, …, VN coins (V1, …VN)
Line 3: N space-separated integers, respectively C1, C2, …, CN

输出格式:

Line 1: A line containing a single integer, the minimum number of coins involved in a payment and change-making. If it is impossible for Farmer John to pay and receive exact change, output -1.

输入输出样例

输入样例#1:

3 70
5 25 50
5 2 1

输出样例#1:

3

说明

Farmer John pays 75 cents using a 50 cents and a 25 cents coin, and receives a 5 cents coin in change, for a total of 3 coins used in the transaction.

题解

转自http://blog.csdn.NET/jkay_wong/article/details/7240588

先说下 01 背包,有n 种不同的物品,每个物品有两个属性size 体积,value 价值,现在给一个容量为 w 的背包,问多可带走多少价值的物品。
int f[w+1]; //f[x] 表示背包容量为x 时的最大价值
for (int i=0; i=size[i]; j++)
f[j] = max(f[j], f[j-size[i]]+value[i]);

如果物品不计件数,就是每个物品不只一件的话,稍微改下即可
for (int i=0; i<n; i++)
for (int j=size[i]; j<=w; j++)
f[j] = max(f[j], f[j-size[i]]+value[i]);

f[w] 即为所求

初始化分两种情况
1、如果背包要求正好装满则初始化 f[0] = 0, f[1~w] = -INF;
2、如果不需要正好装满 f[0~v] = 0;

多重背包问题要求很简单,就是每件物品给出确定的件数,求可得到的最大价值多重背包转换成 01 背包问题就是多了个初始化,
把它的件数C 用分解成若干个件数的集合,这里面数字可以组合成任意小于等于C 的件数,而且不会重复,之所以叫二进制分解,是因为这样分解可以用数字的二进制形式来解释比如:7的二进制 7 = 111 它可以分解成 001 010 100 这三个数可以组合成任意小于等于7 的数,而且每种组合都会得到不同的数
15 = 1111 可分解成 0001 0010 0100 1000 四个数字如果13 = 1101 则分解为 0001 0010 0100 0110 前三个数字可以组合成7以内任意一个数,加上 0110 = 6 可以组合成任意一个大于6 小于13的数,虽然有重复但总是能把 13 以内所有的数都考虑到了,
基于这种思想去把多件物品转换为,多种一件物品,就可用01 背包求解了。

看代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
>     int n;  //输入有多少种物品  
> int c; //每种物品有多少件
> int v; //每种物品的价值
> int s; //每种物品的尺寸
> int count = 0; //分解后可得到多少种物品
> int value[MAX]; //用来保存分解后的物品价值
> int size[MAX]; //用来保存分解后物品体积
> scanf("%d", &n); //先输入有多少种物品,接下来对每种物品进行分解
> while (n--) { //接下来输入n中这个物品
> scanf("%d%d%d", &c, &s, &v); //输入每种物品的数目和价值
> for (int k=1; k<=c; k<<=1) { //<<右移 相当于乘二
> value[count] = k*v;
> size[count++] = k*s;
> c -= k;
> }
> if (c > 0) {
> value[count] = c*v;
> size[count++] = c*s;
> }
> }
>

//现在用count 代替 n 就和01 背包问题完全一样了

所以回到这一题
找钱的=完全背包
自己=多重背包
然后最后枚举答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdlib>
#include<map>
#include<set>
#include<vector>
using namespace std;
int n,t,tt,m,x;
int v[110000],l;
int c[110000];
int f[110000];
int d[110000];
int v1[110000];
int main()
{
scanf("%d%d",&n,&tt);
for (int i=1;i<=n;i++)
scanf("%d",&v1[i]),m=max(m,v1[i]*v1[i]+tt); //找上限
for (int i=1;i<=n;i++)
{
scanf("%d",&x);
int s1=1;
while (s1<x)//把多重背包转化成01背包处理
{
x-=s1;
l++;
v[l]=s1*v1[i];
c[l]=s1;
s1*=2;
}
l++;
v[l]=x*v1[i];
c[l]=x;
}
//完全背包
memset(f,1,sizeof(f));
f[0]=0;
for (int i=1;i<=n;i++)
for (int j=v1[i];j<=m;j++)//注意要用读入的货币面值处理
{
f[j]=min(f[j-v1[i]]+1,f[j]);
}
//多重背包(其实被转成了01背包
memset(d,1,sizeof(d));
int haha=d[1];
d[0]=0;
for (int i=1;i<=l;i++)
for (int j=m;j>=v[i];j--)
d[j]=min(d[j],d[j-v[i]]+c[i]);
int ans=23333333;
for (int i=tt;i<=m;i++)
ans=min(ans,f[i-tt]+d[i]);//给i元,找i-tt元
if (ans>=haha) printf("-1"); else printf("%d",ans);
return 0;
}

P2867 [USACO06NOV]大广场Big Square

题目描述

Farmer John’s cows have entered into a competition with Farmer Bob’s cows. They have drawn lines on the field so it is a square grid with N × N points (2 ≤ N ≤ 100), and each cow of the two herds has positioned herself exactly on a gridpoint. Of course, no two cows can stand in the same gridpoint. The goal of each herd is to form the largest square (not necessarily parallel to the gridlines) whose corners are formed by cows from that herd.
All the cows have been placed except for Farmer John’s cow Bessie. Determine the area of the largest square that Farmer John’s cows can form once Bessie is placed on the field (the largest square might not necessarily contain Bessie).

农民 John 的牛参加了一次和农民 Bob 的牛的竞赛。他们在区域中画了一个 $N$$*$$N$ 的正方形点阵,两个农场的牛各自占据了一些点。当然不能有两头牛处于同一个点。农场的目标是用自己的牛作为4个顶点,形成一个面积最大的正方形(不必须和边界平行) 。 除了 Bessie 以外,FJ其他的牛都已经放到点阵中去了,要确定bessie放在哪个位置,能使得农民约翰的农场得到一个最大的正方形(Bessie不是必须参与作为正方形的四个顶点之一)。

输入输出格式

输入格式:

Line 1: A single integer, N

Lines 2..N+1: Line i+1 describes line i of the field with N characters. The characters are: ‘J’ for a Farmer John cow, ‘B’ for a Farmer Bob cow, and ‘*’ for an unoccupied square. There will always be at least one unoccupied gridpoint.

输出格式:

Line 1: The area of the largest square that Farmer John’s cows can form, or 0 if they cannot form any square.

输入输出样例

输入样例#1:
1
2
3
4
5
6
7
6
J*J***
******
J***J*
******
**B***
******
输出样例#1:

4

题解

这道题有毒?大雾
看到样例感觉是正方形,然后枚边长写了,然后38分
然后以为是长方形,然后写的长方形,然后32分
然后仔细的研究一篇题解(然而似乎都看的那一篇)
发现正方形可以斜着放
我的横坐标纵坐标和题目的xy是反的

图片链不上?
https://cdn.luogu.org/upload/pic/6449.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
using namespace std;
int n;
char c[110][110];
int ans;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i)
scanf("%s",c[i]+1);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{//枚举某一个点
if (c[j][i]=='B') continue;
for (int k=1;k<=i;k++)
for (int l=j+1;l<=n;l++)
{//枚举另一个点
if (c[l][k]=='B') continue;
int x=i-k;
int y=l-j;
int x1=i,y1=j;//求出四个点的左边
int x2=k,y2=l;
int x3=k+y,y3=l+x;
int x4=i+y,y4=j+x;
if (x1<1||y1<1||x2<1||y2<1||x3<1||y3<1||x4<1||y4<1) continue;
if (x1>n||y1>n||x2>n||y2>n||x3>n||y3>n||x4>n||y4>n) continue;
if (c[y3][x3]=='B'||c[y4][x4]=='B') continue;
//有点出界了或者有B
int s=0;//统计四个顶点上有几头牛
if (c[y1][x1]=='J') s++;
if (c[y2][x2]=='J') s++;
if (c[y3][x3]=='J') s++;
if (c[y4][x4]=='J') s++;//统计该正方形上有多少个角有j
if (s>=3) ans=max(ans,x*x+y*y);
//三个角有:放头牛,四个角有:不用放,
//只有满足2种情况的一种才能进行更新
}
}
printf("%d",ans);
return 0;
}

P1879 [USACO06NOV]玉米田Corn Fields

题目描述

Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can’t be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.
农场主John新买了一块长方形的新牧场,这块牧场被划分成M行N列( $1 ≤ M ≤ 12$ ; $1 ≤ N ≤ 12$),每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草,供他的奶牛们享用。
遗憾的是,有些土地相当贫瘠,不能用来种草。并且,奶牛们喜欢独占一块草地的感觉,于是John不会选择两块相邻的土地,也就是说,没有哪两块草地有公共边。
John想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择?(当然,把新牧场完全荒废也是一种方案)

输入输出格式

输入格式:

第一行:两个整数$M$ 和 $N$,用空格隔开。
第2到第$M+1$行:每行包含$N$个用空格隔开的整数,描述了每块土地的状态。第$i+1$行描述了第$i$行的土地,所有整数均为0或1,是1的话,表示这块土地足够肥沃,0则表示这块土地不适合种草。

输出格式:

一个整数,即牧场分配总方案数除以100,000,000的余数。

输入输出样例

输入样例#1:

2 3
1 1 1
0 1 0

输出样例#1:

9

题解

状压dp
存图反过来方便处理
在种不了草的地方不能种草,
本行不能有相邻的,
本行不能和上一行有相邻的,
具体见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
int n,m;
int d[13][1<<13+5];//d[i][j]表示第i行状态为j时方案数
int map[13];//map[i]为读入的状态
int way[1<<13+5];//way[i]表示第i种情况
int w,x;
int ans;
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
scanf("%d",&x);
x=x^1;//反过来存图方便后面位运算
//cout<<x;
map[i]=map[i]<<1|x;//0:适合种草 1:不适合
}
}
int x1=1<<(m);
x1-=1;
for (int i=0;i<=x1;i++)
if ((i&(i<<1))==0) way[++w]=i;//其实就是本行没有相邻的1
//way[i]表示第i种的种草方式状态
for (int i=1;i<=w;i++)
if ((way[i]&map[1])==0)
{
d[1][way[i]]=1;//初始化
}
for (int k=2;k<=n;k++)
for (int i=1;i<=w;i++)//本行状态为i
for (int j=1;j<=w;j++)//上一行状态为j
if (((map[k]&way[i])==0)&&((way[i]&way[j])==0))//本行不在 种不了草的地方放牛
{//本行不和上一行状态冲突
d[k][way[i]]+=d[k-1][way[j]];
d[k][way[i]]%=100000000;
}
for (int i=1;i<=w;i++)
ans=(ans+d[n][way[i]])%100000000;
printf("%d",ans);
return 0;
}

P1005 [NOIp2007]矩阵取数游戏

题目描述

帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的 $n*m$ 的矩阵,矩阵中的每个元素 $ A(i,j) $均为非负整数。游戏规则如下:

1.每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素;

2.每次取走的各个元素只能是该元素所在行的行首或行尾;

3.每次取数都有一个得分值,为每行取数的得分之和, 每行取数的得分 = 被取走的元素值 $*2^i$ ,其中i表示第i次取数(从1开始编号);

4.游戏结束总得分为 m次取数得分之和。

帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。

输入输出格式

输入格式:

输入文件game.in包括n+1行:

第1行为两个用空格隔开的整数n和m。

第2~n+1行为n*m矩阵,其中每行有m个用单个空格隔开的非负整数。

数据范围:

60%的数据满足:1<=n, m<=30,答案不超过10^16

100%的数据满足:1<=n, m<=80,0<=aij<=1000

输出格式:

输出文件game.out仅包含1行,为一个整数,即输入矩阵取数后的最大得分。

输入输出样例

输入样例#1:

1
2
3
2 3
1 2 3
3 4 2

输出样例#1:

1
82

说明

NOIP 2007 提高第三题

题解

高精度挺麻烦的
一行一行的处理,最后加起来

f[i][j]表示取i~j这一段能获得的最大分数(i~j这部分最后取)

初始化:$f_{i,i}=a_i*2^m$

转移方程:

$f{i,j}=max(f{i+1,j}+a{k,i}*2^{m+i-j},f{i,j-1}+a_{k,j}*2^{m+i-j}) $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
using namespace std;
int n,m,lc;
char ch[100];
int d[100];
int a[100][100][100];
int er[81][100];
int A[100];
int B[100];
int ans[200];
int f[81][81][100];
inline void Add(int *b,int *c)//b=b+c
{
memset(d,0,sizeof(d));
d[0]=max(b[0],c[0])+1;
for (int I=1;I<=d[0];I++)//加法
{
d[I]+=b[I]+c[I];//注意是+=
d[I+1]+=(d[I]/10);
d[I]%=10;
}
while (d[d[0]]==0) d[0]--;//去掉0
for (int I=0;I<=d[0];I++) b[I]=d[I];
return;
}
inline void CF(int *b,int *c)//高精度乘法
{
memset(d,0,sizeof(d));//清空
d[0]=b[0]+c[0];
for (int k=1;k<=b[0];k++)//乘
for (int l=1;l<=c[0];l++)
{
d[k+l-1]+=b[k]*c[l];//注意是+=
}
for (int k=1;k<=d[0];k++)//进位
{
d[k+1]+=d[k]/10;
d[k]%=10;
}
while (d[d[0]]==0) d[0]--;//去掉前面的0
for (int k=0;k<=d[0];k++) b[k]=d[k];
}
inline bool Max(int *b,int *c)//比较b数组和c数组哪个大
{
while (b[b[0]]==0&&b[0]>0) b[0]--;//去掉前导0
while (c[c[0]]==0&&c[0]>0) c[0]--;
if (b[0]>c[0]) return true;//长度比较
if (c[0]>b[0]) return false;
for (int i=b[0];i>=1;i--)//一位一位的比
if (b[i]>c[i]) return true; else
if (b[i]<c[i]) return false;//开始少写了这一句
return false;
}
bool flag;
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
scanf("%s",ch+1);//读入
lc=strlen(ch+1);
a[i][j][0]=0;
for (int k=lc;k>=1;k--)
{
a[i][j][++a[i][j][0]]=ch[k]-'0';
}
}
er[0][0]=1;er[0][1]=1;
for (int i=1;i<=m;i++)//预处理2^1~2^m
{
for (int j=0;j<=er[i-1][0];j++)
{
er[i][j]=er[i-1][j];
}
Add(er[i],er[i-1]);
}
for (int k=1;k<=n;k++)//行
{
memset(f,0,sizeof(f));
for (int i=1;i<=m;i++)
{//f[i][i]=a[k][i]*2^m;
Add(f[i][i],a[k][i]);
CF(f[i][i],er[m]);
}
for (int l=1;l<m;l++)
{
for (int i=1,j=i+l;j<=m;i++,j=i+l)
{//这就是dp转移的过程,同状态转移方程
memset(A,0,sizeof(A));
Add(A,a[k][i]);
CF(A,er[m+i-j]);
Add(A,f[i+1][j]);
memset(B,0,sizeof(B));
Add(B,a[k][j]);
CF(B,er[m+i-j]);
Add(B,f[i][j-1]);
flag=Max(A,B);
if (flag)//取max
{
for (int l=0;l<=A[0];l++)
f[i][j][l]=A[l];
} else
{
for (int l=0;l<=B[0];l++)
f[i][j][l]=B[l];
}
}
}
Add(ans,f[1][m]);
}
while (ans[ans[0]]==0&&ans[0]>0) ans[0]--;//去掉0
if (ans[0]==0) ans[0]++;//特判0
for (int i=ans[0];i>=1;i--)//倒着输出
printf("%d",ans[i]);
return 0;
}

P2513 [HAOI2009]逆序对数列

题目描述

对于一个数列{Ai},如果有 $i$$<$$j$ 且 $A_i$$>$$A_j$ ,那么我们称 $A_i$ 与 $A_j$ 为一对逆序对数。若对于任意一个由1~n自然数组成的数列,可以很容易求出有多少个逆序对数。那么逆序对数为 $k$ 的这样自然数数列到底有多少个?

输入输出格式

输入格式:

第一行为两个整数 $n,k$。

输出格式:

写入一个整数,表示符合条件的数列个数,由于这个数可能很大,你只需输出该数对10000求余数后的结果。

输入输出样例

输入样例#1:
1
4 1
输出样例#1:
1
3

说明

样例说明:

下列3个数列逆序对数都为1;分别是1 2 4 3 ;1 3 2 4 ;2 1 3 4;

测试数据范围

30%的数据 $n\le12$

100%的数据 $n\le1000,k\le1000$

题解

用$dp[i][j]$ 表示$1-i$个数,逆序对数为j时的方案数
最后一个数字如果插在第$0$ 个位置,那么逆序对数将增加$i-1$对,插在第$1$个位置逆序对将增加$i-2$ 对.

于是可以很简单的推出状态转移方程了

1
2
3
4
5
6
7
8
9
10
11
12
for (int i=1;i<=n;i++)
{
f[i][0]=1;
for (int j=1;j<=k;j++)
{
for (int l=max(1,i-j);l<=i;l++)
{
f[i][j]+=f[i-1][j-i+l];
}
f[i][j]%=10000;
}
}

然后提交看一下是不是对的.

啥?! A了?! 这数据太水.

然后可以发现,每次转移都是某一段的和,然后可以用前缀和搞,这样每次转移就是O(1)

$s[i][j]$表示$f[i][0]$~$f[i][j]$的和

我分了2类,其实并不需要?因为出现了减法,所以取模的时候要注意下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
int n,k;
int f[1010][1010];
int s[1010][1010];//s[i][j]表示f[i][0]~f[i][j]的和
int main()
{
n=read();k=read();
for (int i=1;i<=n;i++)
{
f[i][0]=1;
s[i][0]=1;
for (int j=1;j<=k;j++)
{

/*for (int l=max(1,i-j);l<=i;l++)
{
f[i][j]+=f[i-1][j-i+l];
}*///手推一下就可以推出来一下转移方程
if (i-j<=1)
{
f[i][j]=((s[i-1][j]-s[i-1][j-i])%10000+10000)%10000;
} else
{
f[i][j]=s[i-1][j];
}
s[i][j]=s[i][j-1]+f[i][j];
s[i][j]=(s[i][j]%10000+10000)%10000;
f[i][j]=(f[i][j]%10000+10000)%10000;
}
}
printf("%d",f[n][k]);
return 0;
}

A了,然后改数据,加极端数据.

极端数据啊,显然可以打表,那就再来两组大数据.

然后 $O(n^3)$ 的就过不了了

注意:负数取模的话,最后再模一下加一下取模,常数小些

其他

其他一些dp题

NOIp考过的(链到xsc博客去了(逃))

  1. 2. NOIP2016 Day1T3 换教室
  2. 3. NOIP2016 Day2T3 愤怒的小鸟
  3. 4. NOIP2015 Day2T2 子串
  4. 5. NOIP2014 Day1T3 飞扬的小鸟