链接: https://pan.baidu.com/s/1TIo0Y3A1Da8w2QMK6FUY1g?pwd=f4f3 提取码: f4f3 复制这段内容后打开百度网盘手机App，操作更方便哦
--来自百度网盘超级会员v6的分享
Tag Archives: DP
POJ 2704(Pascal's Travels-裸dp)
|
Language:
Pascal's Travels
Description
An n x n game board is populated with integers, one nonnegative integer per square. The goal is to travel along any legitimate path from the upper left corner to the lower right corner of the board. The integer in any one square dictates how large a step away
from that location must be. If the step size would advance travel off the game board, then a step in that particular direction is forbidden. All steps must be either to the right or toward the bottom. Note that a 0 is a dead end which prevents any further progress. Consider the 4 x 4 board shown in Figure 1, where the solid circle identifies the start position and the dashed circle identifies the target. Figure 2 shows the three paths from the start to the target, with the irrelevant numbers in each removed. Input
The input contains data for one to thirty boards, followed by a final line containing only the integer -1. The data for a board starts with a line containing a single positive integer n, 4 <= n <= 34, which is the number of rows in this board. This is followed
by n rows of data. Each row contains n single digits, 0-9, with no spaces between them. Output
The output consists of one line for each board, containing a single integer, which is the number of paths from the upper left corner to the lower right corner. There will be fewer than 263 paths for any board.
Sample Input 4 2331 1213 1231 3110 4 3332 1213 1232 2120 5 11101 01111 11111 11101 11101 -1 Sample Output 3 0 7 Hint
Brute force methods examining every path will likely exceed the allotted time limit. 64-bit integer values are available as long values in Java or long long values using the contest's C/C++ compilers.
Source |
就是dp……
一开始忘打‘n’ wa了……
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN (34+1)
int a[MAXN][MAXN],n;
long long f[MAXN][MAXN];
int main()
{
while (scanf("%d",&n)&&n+1)
{
for (int i=1;i<=n;i++)
{
char s[MAXN];
scanf("%s",s+1);
for (int j=1;j<=n;j++) a[i][j]=s[j]-'0';
}
memset(f,0,sizeof(f));f[1][1]=1;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (a[i][j])
{
if (i+a[i][j]<=n) f[i+a[i][j]][j]+=f[i][j];
if (j+a[i][j]<=n) f[i][j+a[i][j]]+=f[i][j];
}
printf("%lldn",f[n][n]);
}
return 0;
}
BZOJ 1084([SCOI2005]最大子矩阵-长矩阵Dp)
1084: [SCOI2005]最大子矩阵
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 586 Solved: 275
[Submit][Status][Discuss]
Description
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。
Input
第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。
Output
只有一行为k个子矩阵分值之和最大为多少。
Sample Input
3 2 2
1 -3
2 3
-2 3
1 -3
2 3
-2 3
Sample Output
9
由于m不超过2
可以暴力Dp
分为m=1和m=2种情况
m=1就不用说了，
F[i][j][k]表示第1行到i第二行到j所能取到的最小值
#include<cstdio>
#include<cstring>
#include<iostream>
#include<functional>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define MAXN (100+10)
#define MAXM (2+1)
#define MAXK (10+1)
int f[MAXN][MAXK],F[MAXN][MAXN][MAXK],n,m,k;
int a[MAXN][MAXN],sum[MAXN][MAXN];
int main()
{
scanf("%d%d%d",&n,&m,&k);
sum[0][1]=sum[0][2]=0;
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&a[i][j]),sum[i][j]=sum[i-1][j]+a[i][j];
if (m==1)
{
memset(f,0,sizeof(f));
for (int i=1;i<=n;i++)
{
f[i][0]=0;
for (int l=1;l<=k;l++)
{
f[i][l]=f[i-1][l];
for (int j=0;j<i;j++)
{
f[i][l]=max(f[i][l],f[j][l-1]+sum[i][1]-sum[j][1]);
}
}
}
cout<<f[n][k]<<endl;
}
else
{
memset(F,0,sizeof(F));
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
F[i][j][0]=0;
for (int l=1;l<=k;l++)
{
F[i][j][l]=max(F[i-1][j][l],F[i][j-1][l]);
for (int i2=0;i2<i;i2++) F[i][j][l]=max(F[i][j][l],F[i2][j][l-1]+sum[i][1]-sum[i2][1]);
for (int j2=0;j2<j;j2++) F[i][j][l]=max(F[i][j][l],F[i][j2][l-1]+sum[j][2]-sum[j2][2]);
if (i==j)
for (int j2=0;j2<i;j2++)
{
F[i][i][l]=max(F[i][i][l],F[j2][j2][l-1]+sum[i][1]-sum[j2][1]+sum[j][2]-sum[j2][2]);
}
}
}
}
cout<<F[n][n][k]<<endl;
}
return 0;
}
FZU 1040(基因序列相似性问题-CLCS)
Problem 1040 基因序列相似性问题
Accept: 59 Submit: 548
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
Genotype 是一个有限的基因序列集。它的每个成员都是由大写的英文字母A-Z组成，不同的字母表示不同种类的基因。一个基因种类可以分化成为若干新的基因种类。这种分化一般呈树状结构。树根处的基因序列称为母序列。基因序列中含有母序列的基因子序列称为本质基因子序列。生物信息学家们在研究Genotype 基因序列时，需要研究同一种类基因序列的相似性。对于同一种类的2个基因序列X和Y，已知它们的母序列P，基因序列X和Y的最长公共本质基因子序列给出其相似性的准确刻画。为了有效地分析基因序列的相似性，科学家们希望设计出一个高效的计算程序，能对给定的基因序列X，Y和它们的母序列P，快速计算出基因序列X和Y的最长公共本质基因子序列的长度。
编程任务:
给定基因序列X，Y和母序列P，计算出基因序列X和Y的最长公共本质基因子序列的长度。
Input
输入数据的前3行中每行有一个正整数，分别表示序列X，Y和P的长度m，n和r（1≤m,n,r≤1000）。接下来的3行给出序列X，Y和P。
Output
在屏幕上输出基因序列X和Y的最长公共本质基因子序列的长度。如果基因序列X和Y没有以P为母序列的公共本质基因子序列，则输出0。
Sample Input
331ABCBCAA
Sample Output
1
这题是为了找省选题无意发现的，原问题的加强版。
解法：
首先我有一个用i滚动的做法，反正是T了，正误不明。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXN (1000+10)
int f[2][MAXN][MAXN];
char a[MAXN],b[MAXN],c[MAXN];
int n,m,p;
int main()
{
freopen("fzu1040.out","r",stdin);
while (scanf("%d%d%d",&n,&m,&p)==3)
{
scanf("%s%s%s",a+1,b+1,c+1);
memset(f,0,sizeof(f));
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
for (int k=0;k<=min(i,j);k++)
{
f[i%2][j][k]=max(f[i%2][j-1][k],f[(i-1)%2][j][k]);
if (k&&(a[i]==b[j]&&b[j]==c[k])&&(f[(i-1)%2][j-1][k-1]||k==1)) f[i%2][j][k]=max(f[(i-1)%2][j-1][k-1]+1,f[i%2][j][k]);
if ((a[i]==b[j])&&(f[(i-1)%2][j-1][k]||k==0)) f[i%2][j][k]=max(f[(i-1)%2][j-1][k]+1,f[i%2][j][k]);
}
for(int j=1;j<=m;j++)
for (int k=1;k<=p;k++)
f[(i+1)%2][j][k]=0;
}
if (f[n%2][m][p]<p) cout<<"0"<<endl;
else cout<<f[n%2][m][p]<<endl;
}
return 0;
}
找到反例请回复我.
再来说说正解(输出时记得输的是f[p%2][n][m]不是f[k%2][n][m]，变量名乱设害死人）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXN (1000+10)
int f[2][MAXN][MAXN];
char a[MAXN],b[MAXN],c[MAXN];
int n,m,p;
int main()
{
// freopen("fzu1040.out","r",stdin);
while (scanf("%d%d%d",&n,&m,&p)!=EOF)
{
scanf("%s%s%s",a+1,b+1,c+1);
memset(f,0,sizeof(f));
int k=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
if (a[i]==b[j]) f[k][i][j]=f[k][i-1][j-1]+1;
else f[k][i][j]=max(f[k][i][j-1],f[k][i-1][j]);
}
bool flag=1;
int ta=MAXN,tb=MAXN,mina=1,minb=1;
for (int k=1;k<=p&&flag;k++)
{
flag=0;
for (int i=mina-1;i<=n;i++)
for (int j=minb-1;j<=m;j++)
f[k%2][i][j]=0;
for (int i=mina;i<=n;i++)
for (int j=minb;j<=m;j++)
{
f[k%2][i][j]=0;
if ((a[i]==b[j]&&b[j]==c[k])&&(f[(k%2)^1][i-1][j-1]||k==1))
{
f[k%2][i][j]=f[(k%2)^1][i-1][j-1]+1;
flag=1;ta=min(ta,i);tb=min(tb,j);
}
else if (a[i]==b[j]&&b[j]==c[k]) continue;
else if ((a[i]==b[j])&&(f[k%2][i-1][j-1])) f[k%2][i][j]=max(f[k%2][i-1][j-1]+1,f[k%2][i][j]);
else if (a[i]==b[j]) continue;
else f[k%2][i][j]=max(f[k%2][i][j-1],f[k%2][i-1][j]);
}
mina=ta;minb=tb;
ta=tb=MAXN;
}
/*
if (!flag)
{
if (f[k%2][n][m]>=k) while (1);
}
*/
if (!flag) printf("0n");
else printf("%dn",f[p%2][n][m]);
}
return 0;
}
很直观的Dp。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXN (1000+10)
int f[2][MAXN][MAXN];
char a[MAXN],b[MAXN],c[MAXN];
int n,m,p;
int main()
{
// freopen("fzu1040.out","r",stdin);
while (scanf("%d%d%d",&n,&m,&p)!=EOF)
{
scanf("%s%s%s",a+1,b+1,c+1);
memset(f,0,sizeof(f));
int k=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
if (a[i]==b[j]) f[k][i][j]=f[k][i-1][j-1]+1;
else f[k][i][j]=max(f[k][i][j-1],f[k][i-1][j]);
}
bool flag=1;
int ta=MAXN,tb=MAXN,mina=1,minb=1;
for (int k=1;k<=p&&flag;k++)
{
flag=0;
for (int i=mina-1;i<=n;i++)
for (int j=minb-1;j<=m;j++)
f[k%2][i][j]=0;
for (int i=mina;i<=n;i++)
for (int j=minb;j<=m;j++)
{
f[k%2][i][j]=max(f[k%2][i][j-1],f[k%2][i-1][j]);
if (k&&(a[i]==b[j]&&b[j]==c[k])&&(f[(k%2)^1][i-1][j-1]||k==1))
{
f[k%2][i][j]=max(f[(k%2)^1][i-1][j-1]+1,f[k%2][i][j]);
flag=1;ta=min(ta,i);tb=min(tb,j);
}
if ((a[i]==b[j])&&(f[k%2][i-1][j-1])) f[k%2][i][j]=max(f[k%2][i-1][j-1]+1,f[k%2][i][j]);
}
mina=ta;minb=tb;
ta=tb=MAXN;
}
/*
if (!flag)
{
if (f[k%2][n][m]>=k) while (1);
}
*/
if (!flag) printf("0n");
else printf("%dn",f[p%2][n][m]);
}
return 0;
}
要考虑从f[k-1][i-1][j-1],f[k][i-1][j-1],f[k][i-1][j],f[k][i][j-1]转移的情况,输出记得清0.
事实上，关于数组清0部分，我们还可以做得更好
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXN (1000+10)
int f[2][MAXN][MAXN];
char a[MAXN],b[MAXN],c[MAXN];
int n,m,p;
int main()
{
// freopen("fzu1040.out","r",stdin);
while (scanf("%d%d%d",&n,&m,&p)!=EOF)
{
scanf("%s%s%s",a+1,b+1,c+1);
memset(f,0,sizeof(f));
int k=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
if (a[i]==b[j]) f[k][i][j]=f[k][i-1][j-1]+1;
else f[k][i][j]=max(f[k][i][j-1],f[k][i-1][j]);
}
bool flag=1;
int ta=MAXN,tb=MAXN,mina=1,minb=1;
for (int k=1;k<=p&&flag;k++)
{
flag=0;
for (int i=mina-1;i<=n;i++)
f[k%2][i][minb-1]=0;
for (int j=minb-1;j<=m;j++)
f[k%2][mina-1][j]=0; //只要把边界情况赋0
for (int i=mina;i<=n;i++)
for (int j=minb;j<=m;j++)
{
f[k%2][i][j]=max(f[k%2][i][j-1],f[k%2][i-1][j]);
if (k&&(a[i]==b[j]&&b[j]==c[k])&&(f[(k%2)^1][i-1][j-1]||k==1))
{
f[k%2][i][j]=max(f[(k%2)^1][i-1][j-1]+1,f[k%2][i][j]);
flag=1;ta=min(ta,i);tb=min(tb,j);
}
if ((a[i]==b[j])&&(f[k%2][i-1][j-1])) f[k%2][i][j]=max(f[k%2][i-1][j-1]+1,f[k%2][i][j]);
}
mina=ta;minb=tb;
ta=tb=MAXN;
}
if (!flag) printf("0n");
else printf("%dn",f[p%2][n][m]);
}
return 0;
}
不妨把对k=0的特判写在一起
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXN (1000+10)
int f[2][MAXN][MAXN];
char a[MAXN],b[MAXN],c[MAXN];
int n,m,p;
int main()
{
// freopen("fzu1040.out","r",stdin);
c[0]=' ';
while (scanf("%d%d%d",&n,&m,&p)!=EOF)
{
scanf("%s%s%s",a+1,b+1,c+1);
bool flag=1;
int ta=MAXN,tb=MAXN,mina=1,minb=1;
for (int k=0;k<=p&&flag;k++)
{
flag=0;
for (int i=mina-1;i<=n;i++)
f[k%2][i][minb-1]=0;
for (int j=minb-1;j<=m;j++)
f[k%2][mina-1][j]=0;
for (int i=mina;i<=n;i++)
for (int j=minb;j<=m;j++)
{
f[k%2][i][j]=max(f[k%2][i][j-1],f[k%2][i-1][j]);
if (k&&(a[i]==b[j]&&b[j]==c[k])&&(f[(k%2)^1][i-1][j-1]||k==1))
{
f[k%2][i][j]=max(f[(k%2)^1][i-1][j-1]+1,f[k%2][i][j]);
flag=1;ta=min(ta,i);tb=min(tb,j);
}
if ((a[i]==b[j])&&(f[k%2][i-1][j-1]||k==0)) f[k%2][i][j]=max(f[k%2][i-1][j-1]+1,f[k%2][i][j]);
}
mina=ta;minb=tb;
ta=tb=MAXN;
if (!k)
{
flag=1;mina=minb=1;
}
}
if (!flag) printf("0n");
else printf("%dn",f[p%2][n][m]);
}
return 0;
}
跳跃(处理操作迭代-等价替代)
Problem2 跳跃(jump.cpp/c/pas)
【题目描述】
一开始你位于数轴上的x位置，一次跳跃你可以从x跳跃到（9x+4）mod 1000000007或者（27x+13）mod 1000000007。求跳回到原点的最少跳跃次数。
保证通过有限次跳跃可以回到原点。
【输入格式】
一行一个整数x表示你的初始坐标，保证0<=x<1000000007
【输出格式】
一行一个整数表示最小的跳跃次数。
【样例输入】
555555559
【样例输出】
1
【数据范围】
对于40%的数据，答案<=20
对于100%的数据，答案<=100000
神结论：
9x+4等价于2次3x+1
27x+13等价于3次3x+1
#include<cstdio>
#include<iostream>
#include<functional>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
#define MAXN (100000)
#define F (1000000007)
long long x;
int main()
{
freopen("jump.in","r",stdin);
freopen("jump.out","w",stdout);
while (scanf("%d",&x)==1)
{
int ans=0;
for (;!((!x)&&ans!=1);x=(3*x+1)%F) ans++;
printf("%dn",ans/3+bool(ans%3));
}
return 0;
}
子序列(省略已知值法与挪位得解法)
Problem 1 子序列(subsequence.pas/c/cpp)
【题目描述】
给定一个长度为N（N为偶数）的序列，问能否将其划分为两个长度为N/2的严格递增子序列，
【输入格式】
若干行，每行表示一组数据。对于每组数据，首先输入一个整数N，表示序列的长度。之后N个整数表示这个序列。
【输出格式】
同输入行数。对于每组数据，如果存在一种划分，则输出“Yes!”，否则输出“No!“。
【样例输入】
6 3 1 4 5 8 7
6 3 2 1 6 5 4
【样例输出】
Yes!
No!
【数据范围】
共三组数据，每组数据行数<=50，0 <= 输入的所有数 <= 10^9
第一组(30%)：N <= 20
第二组(30%)：N <= 100
第三组(40%)：N <= 2000
一般青年Dp方案：F[i][j][k][l] 表示前i+j位分为一个长度为i以j结尾，一个长度为k以l结尾的序列
是否可行(0,1)
省略已知值：观察发现j和l中至少有一个为a[i+j]
故可省略其中一位
n=2000必跪
文艺青年Dp方案：
挪位得解：把f[i][j][k]中的k挪出来
原因：显然i和j不变时，我们希望k越小越好
所以记录min(k)，并记录无解情况
O(n^2)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
#define MAXN (2000+10)
#define INF (2139062143)
int n,a[MAXN],f[MAXN][MAXN];
int main()
{
freopen("subsequence.in","r",stdin);
freopen("subsequence.out","w",stdout);
while (scanf("%d",&n)!=EOF)
{
memset(f,127,sizeof(f));
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
f[1][1]=-1;
for (int i=1;i<n;i++)
{
for (int j=1;j<=i;j++)
{
if (f[i][j]!=INF)
{
if (a[i]<a[i+1]) f[i+1][j+1]=min(f[i+1][j+1],f[i][j]);
if (f[i][j]<a[i+1])
f[i+1][i-j+1]=min(f[i+1][i-j+1],a[i]);
}
}
}
/*
for (int i=0;i<=n;i++)
{
for (int j=0;j<=n;j++)
printf("%d ",f[i][j]);
printf("n");
}
*/
if (f[n][n>>1]!=INF) printf("Yes!n");
else printf("No!n");
}
return 0;
}
fzu_noip 1036(磁盘碎片整理-Dp)
磁盘碎片整理
时限：1s
内存：32M
★问题描述:
Jack最近在PS海报。海报所需各种素材不但让Jack头大，也让硬盘分区中的文件碎片越来越多，电脑的反应速度越来越慢。
烦恼的Jack决定好好整理一下磁盘的碎片。但是，为了体现高手风范，自负的Jack不喜欢系统自带的整理工具，决定自己编写一个，希望你帮他完成简单的第一遍整理。
因为不可移动的系统文件的分隔，Jack的N个文件，分为许多文件块，杂乱分布在M个长度不等的区间中。在第一遍整理时，只将每个区间中的碎片进行顺序改变，不跨区间移动。
因为在Jack完成的第二次整理时，将把M个区间依顺序连接成一个完整区间，希望整理完成后，零碎度越低越好。（若连接后的完整区间，文件块i与文件块i+1属于不同文件，则零碎度+1）。
例：
N=5 M=3
存储区间1：长度3 文件块[4,3,1]
存储区间2：长度4 文件块[2,1,4,4]
存储区间3：长度3 文件块[1,3,1]
第一次整理，第二次连接后：[1,3,4][4,4,2,1][1,1,3]，零碎度为5
★数据输入：
第一行n m(1<=n<=10,1<=m<=10000),表示有n个文件，m个存储区间。
接下来m行，每行第一个整数为Li（0<Li<=50），表示存储区间i的长度。接下来Li个整数，分别表示该区间第j文件块所属文件。
★结果输出:
输出两次整理完成后，能达到的最小零碎度。
|
输入示例 |
输出示例 |
|
5 3 3 4 3 1 4 2 1 4 4 3 1 3 1 |
5
|
简单Dp，f[i][j]表示到第i块硬盘前面接j能取得的最大头尾连接数(开始那个默认与之前的连接），则
F[i][j]=| max(f[i][l[j]],f[i-1][k]+(b[i-1][l[j]]&&(k!=l[j]||pre_size==1))) (i>1)
|1
(i=1)
答案为tot-max(f[m][k](0<=k<n)) tot为每个区间不同数字类数的总和
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
#define MAXN (10)
#define MAXM (10000+10)
#define MAXLi (50)
int n,m;
bool b[MAXM][11];
int f[MAXM][11];
int l[MAXN];
int main()
{
// freopen("piece.in","r",stdin);
memset(b,0,sizeof(b));
memset(f,0,sizeof(f));
scanf("%d%d",&n,&m);
int ans=0,pre_size=0;
for (int i=1;i<=m;i++)
{
int li;
scanf("%d",&li);
for (int j=1;j<=li;j++) scanf("%d",&l[j]);
sort(l+1,l+li+1);
int size=unique(l+1,l+li+1)-(l+1);
ans+=size;
// cout<<size<<endl;
// for (int i=1;i<=size;i++) cout<<l[i]<<' ';cout<<endl;
for (int j=1;j<=size;j++)
b[i][l[j]]=1;
if (i==1)
{
for (int j=1;j<=size;j++)
f[1][l[j]]=1;
}
else
{
for (int j=1;j<=size;j++)
for (int k=0;k<n;k++)
if (b[i-1][k])
{
f[i][l[j]]=max(f[i][l[j]],f[i-1][k]+(b[i-1][l[j]]&&(k!=l[j]||pre_size==1)));
}
}
pre_size=size;
}
int p=0;
for (int j=0;j<n;j++) {p=max(p,f[m][j]); }
/*
for (int i=1;i<=m;i++)
{
for (int j=0;j<n;j++)
cout<<f[i][j]<<' ';
cout<<endl;
}
*/
cout<<ans-p<<endl;
// while (1);
return 0;
}
BZOJ 1088(mine)
1088: [SCOI2005]扫雷Mine
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 659 Solved: 386
[Submit][Status][Discuss]
Description
相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷，要你根据一些信息找出雷来。万圣节到了，“余”人国流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，如下图： 由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。
Input
第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<= N <= 10000）
Output
一个数，即第一列中雷的摆放方案数。
Sample Input
2
1 1
1 1
Sample Output
2
Dp扫雷题：
一开始居然没有想出方程…天生不敏感？
显然方程为f(i,x,x_r) 表示第i格时，中间x和右边x_r是否有雷
轻易得到递归方程：
这题的教训是，方程果断列，另当前状态确定差1，由前面得到。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<cmath>
using namespace std;
#define MAXN (10000+10)
int n,a[MAXN];
int f[MAXN][2][2]={0}; //Middle and 1
int main()
{
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
switch (a[1])
{
case 2:f[1][1][1]++;break;
case 0:f[1][0][0]++;break;
default:f[1][0][1]=f[1][1][0]=1;
}
for (int i=2;i<=n;i++)
{
switch (a[i])
{
case 3:f[i][1][1]=f[i-1][1][1];break;
case 0:f[i][0][0]=f[i-1][0][0];break;
case 2:f[i][1][0]=f[i-1][1][1];f[i][0][1]=f[i-1][1][0];f[i][1][1]=f[i-1][0][1];break;
case 1:f[i][1][0]=f[i-1][0][1];f[i][0][1]=f[i-1][0][0];f[i][0][0]=f[i-1][1][0];break;
}
}
cout<<f[n][1][0]+f[n][0][0]<<endl;
return 0;
}
CF 254E(从当前向后递推)
Dp题，主要推方程。
显然每天从食量最小的贪起。
为了处理食物隔夜问题，多留一维表示昨天剩下的食物。
由于不好求出向前的方程，也不知道终态，所以要从当前向后递推（而非从前面向当前递推，类似矿工食堂的解决方案）
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iostream>
#include<vector>
using namespace std;
#define MAXN (400+10)
#define MAXV (400+10)
#define MAXAi (400+10)
#define MAXM (400+10)
#define TomorrowFood (min(a[i],x))
#define _Next_ [i+1][TomorrowFood]
int n,m,v;
vector <pair< int,int> > man[MAXN]; // ith day jth man eat k food. //pair(j,k)
int a[MAXN]={0};
int f[MAXN][MAXV*2]={0}; // ith day havv j food left last night,->rat
int totlastf[MAXN][MAXV*2]={0}; //昨晚几个人吃
int last[MAXN][MAXV*2]={0}; //昨晚剩多少
int solve(int i,int j)
{
if (i>2) solve(i-1,last[i][j]); //{ n+1->n n->n-1 ... 2->1 } 1->0
cout<<totlastf[i][j];
for (int k=1;k<=totlastf[i][j];k++)
cout<<' '<<man[i-1][k].second;
cout<<endl;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>n>>v;
for (int i=1;i<=n;i++){cin>>a[i]; man[i].push_back(make_pair(0,0)); }
cin>>m;
for (int i=1;i<=m;i++)
{
int l,r,fi; cin>>l>>r>>fi; //fi=food in a man
for (int j=l;j<=r;j++)
man[j].push_back(make_pair(fi,i));
}
for (int i=1;i<=n;i++) sort(man[i].begin(),man[i].end());
memset(f,128,sizeof(f));
f[1][0]=0;
for (int i=1;i<=n;i++)
{
for (int j=0;j<=a[i-1];j++) //昨晚最多留下a[i] food(其它过期）
{
int x=j-v+a[i]; //表示昨天剩下的，吃了v，又多了今天的a[i]
if (x<0) continue; //一定够吃
if (f[i+1][TomorrowFood]<f[i][j])
{
f[i+1][TomorrowFood]=f[i][j];
totlastf[i+1][TomorrowFood]=0;
last _Next_ =j;
}
for (int k=1;k<man[i].size();k++)
{
x-=man[i][k].first;
if (x<0) break;
if (f[i+1][TomorrowFood]<f[i][j]+k)
{
f[i+1][TomorrowFood]=f[i][j]+k;
totlastf[i+1][TomorrowFood]=k;
last _Next_ =j;
}
}
}
}
int ans=-1,now;
for (int j=0;j<=MAXV;j++)
if (ans<f[n+1][j]) {ans=f[n+1][j]; now=j; }
cout<<ans<<endl;
solve(n+1,now);
return 0;
}
POJ 2355(区间最大值-zkw线段树优化Dp方程）
|
Language:
Railway tickets
Description
从1号车站Ekaterinburg到n号车站Sverdlovsk有一条铁路。
 订票时票价如下
由于总总原因，距离超过L3的车票不能定。
现在你打算从s号车站乘铁路到t号车站，求最小费用。
Input
第一行有6个数 L1, L2, L3, C1, C2, C3 (1 <= L1 < L2 < L3 <= 10^9, 1 <= C1 < C2 < C3 <= 10^9)
第二行为车站数N (2 <= N <= 10000)
第三行为s和t，表示起点和终点.
接下来n-1行，表示从第1好车站到第i(1<i<=n)号车站的距离（保证是升序）.
Output
仅一行，为最小费用(<10^9)
Sample Input 3 6 8 20 30 40 7 2 6 3 7 8 13 15 23 Sample Output 70 Source |
这题就是Dp
显然F[i]=F[j]+c[k](j<i,a[j]-a[i]<=l[k],1<=k<=3) F[i]表示从起点s到车站i的最小费用。
用显然j单调递增，可用指针向后推（O(n)）
注意判断INF为无解情况，可能超过变成负数，线段树记得开大
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<cctype>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (20000+10)
#define INF (2139062143)
int l[4],c[4],n,a[MAXN],st,en;
struct SegMentTree
{
int t[MAXN*10],n,M;
SegMentTree(){}
SegMentTree(int _n):n(_n)
{
M=1;while (M-2<n) M<<=1;
memset(t,127,sizeof(t));
}
void update(int x)
{
for (x>>=1;x;x>>=1) t[x]=min(t[x<<1],t[(x<<1)^1]);
}
void insert(int x,int c)
{
x+=M;
if (t[x]>c)
{
t[x]=c;//cout<<endl<<'I'<<x<<' '<<c<<endl;
update(x);
}
}
int find(int l,int r)
{
if (l>r) return INF;
l=l-1+M;r=r+1+M;
int ans=INF;
while (l^r^1)
{
if (~l&1) ans=min(ans,t[l+1]);
if (r&1) ans=min(ans,t[r-1]);
l>>=1;r>>=1;
}
return ans;
}
}t;
void push(int &j,int L,int i)
{
while (a[i]-a[j]>L) j++;
}
int main()
{
scanf("%d%d%d%d%d%d%d",&l[1],&l[2],&l[3],&c[1],&c[2],&c[3],&n);
t=SegMentTree(n);
scanf("%d%d",&st,&en);if (st>en) swap(st,en);
if (st==en) {cout<<"0"<<endl;return 0; }
a[1]=0;
for (int i=2;i<=n;i++)
{
scanf("%d",&a[i]);
}
int j[4]={st,st,st,st};
t.insert(st,0);
for (int i=st+1;i<=en;i++)
{
int value=INF;
for (int k=1;k<=3;k++)
{
push(j[k],l[k],i);
// cout<<j[k]<<' ';
int p=t.find(j[k],i-1);
if (p<INF) p+=c[k];
value=min(value,p);
}
// cout<<value<<' '<<endl;
t.insert(i,value);
// for (int i=1;i<=t.M*2;i++) if (t.t[i]-INF) cout<<i<<' '<<t.t[i]<<' ';
// cout<<endl;
}
cout<<t.find(en,en)<<endl;
return 0;
}