A - 数字三角形
题解:
假设getMax(i,j)表示点(i,j)到底部的最长路径,
那么getMax(i,j)=max(getMax(i+1,j),getMax(i+1,j+1))+triangle[i][j];
用maxSum[i][j]存取中间结果;
- 记忆化搜索
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=105;
int triangle[MAXN][MAXN];
int maxSum[MAXN][MAXN];
int n;
int getMax(int i,int j)
{
if(i==n) return maxSum[i][j]=triangle[i][j];
if(maxSum[i][j]!=-1) return maxSum[i][j];
return maxSum[i][j]=max(getMax(i+1,j),getMax(i+1,j+1))+triangle[i][j];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
scanf("%d",&triangle[i][j]);
}
}
memset(maxSum,-1,sizeof(maxSum));
printf("%d\n",getMax(1,1));
}
- 嵌套循环
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=105;
int triangle[MAXN][MAXN];
int dp[MAXN][MAXN];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
scanf("%d",&triangle[i][j]);
}
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
dp[i][j]=max(dp[i-1][j-1]+triangle[i][j],dp[i-1][j]+triangle[i][j]);
}
}
int res=0;
for(int i=1;i<=n;i++)
{
res=max(res,dp[n][i]);
}
printf("%d\n",res);
}
母牛的故事
题意:
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
题解:
假设第n年母牛的数量为f(n),则第n年的母牛的数量等于原来的旧的母牛数量加上新出生的母牛数量,旧的母牛数量等于f(n-1),因为小母牛从第四年开始才初生一头母牛,也就是三年前的母牛才有生小母牛的能力,所以新产生的母牛的数量等于三年前的母牛的数量
- 记忆化搜索:
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=60;
int sum[60];
int f(int n)
{
if(sum[n]!=-1) return sum[n];
if(n<5) return sum[n]=n;
return sum[n]=f(n-1)+f(n-3);
}
int main()
{
memset(sum,-1,sizeof(sum));
int n;
while(scanf("%d",&n)!=EOF,n)
{
printf("%d\n",f(n));
}
}
- 嵌套循环:
#include<cstdio>
using namespace std;
const int MAXN=60;
int dp[60];
int main()
{
for(int i=1;i<=4;i++)
{
dp[i]=i;
}
for(int i=5;i<55;i++)
{
dp[i]=dp[i-1]+dp[i-3];
}
int n;
while(scanf("%d",&n)!=EOF,n)
{
printf("%d\n",dp[n]);
}
}
平面划分问题
注明出处，摘自 http://www.cnblogs.com/chaosheng/archive/2012/01/26/2329583.html
(1) n条直线最多分平面问题
题目大致如:n条直线，最多可以把平面分为多少个区域。
析:可能你以前就见过这题目，这充其量是一道初中的思考题。但一个类型的题目还是从简单的入手，才容易发现规律。当有n-1条直线时，平面最多被分成了f（n-1）个区域。则第n条直线要是切成的区域数最多，就必须与每条直线相交且不能有同一交点。这样就会得到n-1个交点。这些交点将第n条直线分为2条射线和n-2条线断。而每条射线和线断将以有的区域一分为二。这样就多出了2+（n-2）个区域。
故：f(n)=f(n-1)+n=f(n-2)+(n-1)+n= ……=f(1)+1+2+……+n =n(n+1)/2+1
(2) 折线分平面（hdu2050）
根据直线分平面可知，由交点决定了射线和线段的条数，进而决定了新增的区域数。当n-1条折线时，区域数为f（n-1）。为了使增加的区域最多，则折线的两边的线段要和n-1条折线的边，即2*（n-1）条线段相交。那么新增的线段数为4*（n-1），射线数为2。但要注意的是，折线本身相邻的两线段只能增加一个区域。
故f(n)=f(n-1)+4(n-1)+2-1
=f(n-1)+4(n-1)+1
=f(n-2)+4(n-2)+4(n-1)+2
……
=f(1)+4+4*2+……+4(n-1)+(n-1)
=2n^2-n+1
(3) 封闭曲线分平面问题
题目大致如设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。
析：当n-1个圆时，区域数为f(n-1).那么第n个圆就必须与前n-1个圆相交，则第n个圆被分为2（n-1）段线段，增加了2（n-1）个区域。
故： f(n)=f(n-1)+2(n-1)=f(1)+2+4+……+2(n-1) =n^2-n+2
(4)平面分割空间问题（hdu1290）
由二维的分割问题可知，平面分割与线之间的交点有关，即交点决定射线和线段的条数，从而决定新增的区域数。试想在三维中则是否与平面的交线有关呢？当有n-1个平面时，分割的空间数为f（n-1）。要有最多的空间数，则第n个平面需与前n-1个平面相交，且不能有共同的交线。即最多有n-1 条交线。而这n-1条交线把第n个平面最多分割成g（n-1）个区域。（g（n）为（1）中的直线分平面的个数）此平面将原有的空间一分为二，则最多增加g（n-1）个空间。
故：f(n)=f(n-1)+g(n-1) ps:g(n)=n(n+1)/2+1
=f(n-2)+g(n-2)+g(n-1)
……
=f(1)+g(1)+g(2)+……+g(n-1)
=2+(1*2+2*3+3*4+……+(n-1)n)/2+（n-1）
=(1+22+32+42+……+n2-1-2-3-……-n )/2+n+1
=(n^3+5n)/6+1
折线分割平面
题解:
#include<cstdio>
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%d\n",2*n*n-n+1);
}
}
平面分割球体
题解:
#include<cstdio>
int main()
{
int n;
while(~scanf("%d",&n))
printf("%d\n",(n*n*n+5*n)/6+1);
}
Working out
题意:
有n*m个格子, 走过一个格子可以得到相应的分数.一个人从左上角出发走到右下角,只能向左走或者向下走;另一个人从左下角出发走到右上角,只能向右走或者向上走;中途两个人只能有一次相遇,相遇的方格的分数不算进去,问两个人能得到的最大分数;
题解:
- 因为两个人只能相遇一次,所以相遇点不能在边上
- 假设A向下一步到相遇点,那么B不能向上走一步到相遇点,为了只相遇一次,A只能再继续向下走;同时,B向右走,B继续向右走;
- 同理,假设A向右一步走到相遇点,A继续向右走;B向上走一步到相遇点,B继续向右走;
- 四个方向的dp
dp1[i][j] := 从 (1, 1) 到 (i, j) 的最大分数
dp2[i][j] := 从 (i, j) 到 (n, m) 的最大分数
dp3[i][j] := 从 (n, 1) 到 (i, j) 的最大分数
dp4[i][j] := 从 (i, j) 到 (1, m) 的最大分数
则分数的最大值对应上面的两种情况
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1005;
int dp1[MAXN][MAXN];
int dp2[MAXN][MAXN];
int dp3[MAXN][MAXN];
int dp4[MAXN][MAXN];
int graph[MAXN][MAXN];
int n,m;
void init()
{
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
memset(dp3,0,sizeof(dp3));
memset(dp4,0,sizeof(dp4));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
dp1[i][j]=max(dp1[i][j-1],dp1[i-1][j])+graph[i][j];
}
}
for(int i=n;i>=1;i--)
{
for(int j=m;j>=1;j--)
{
dp2[i][j]=max(dp2[i][j+1],dp2[i+1][j])+graph[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=m;j>=1;j--)
{
dp3[i][j]=max(dp3[i][j+1],dp3[i-1][j])+graph[i][j];
}
}
for(int i=n;i>=1;i--)
{
for(int j=1;j<=m;j++)
{
dp4[i][j]=max(dp4[i][j-1],dp4[i+1][j])+graph[i][j];
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&graph[i][j]);
}
}
init();
int ans=0;
for(int i=2;i<n;i++)
{
for(int j=2;j<m;j++)
{
ans=max(ans,dp1[i-1][j]+dp2[i+1][j]+dp3[i][j+1]+dp4[i][j-1]);
ans=max(ans,dp1[i][j-1]+dp2[i][j+1]+dp3[i-1][j]+dp4[i+1][j]);
}
}
printf("%d\n",ans);
}
排列计数
排列计数的第一维一般是1~i的排列的方案数，第二维第三维根据条件来定义
Attack on Titans
题意:
有R,G,B三种士兵,一共有n个;求至少有m个连续G士兵，最多有k个连续R士兵的排列的种数。
题解:
先把问题都转化成至多连续的情况：
至少m个连续G,至多k个连续R
=至多n个连续G,至多k个连续连续R 减去 至多k个连续R，至多（m-1）个连续G
dp[i][j] 至多有u个连续G，至多有v个连续R的个数,u,v为常数
dp[i][0]表示第i个位置放G且至多有u个连续G，至多有v个连续R
dp[i][1]表示第i个位置放R且至多有u个连续G，至多有v个连续R
dp[i][2]表示第i个位置放P且至多有u个连续G，至多有v个连续R
- 当第i个为P,前一个怎么放都可以
dp[i][2]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2] - 当第i个为G时
- 如果i<=u 时 无论前一个怎么放都不会超过u个连续的G士兵
- dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]
- 如果i=u+1时，要排除前u个都放了G的情况
- dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-1;
- 当 i > u + 1时，我们最担心的是什么？第i - 1 到 i - u都是G士兵，那么此时在i号位置放置G士兵，也将不符合约束
我们可以减去不符合约束的方案数，当 i - 1 到 i - u都是G士兵时 有多少种方案？肯定当位置i - u -1是R或者P啦 - dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-dp[i-u-1][1]-dp[i-u-1][2]
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int MAXN=1000010;
const LL MOD=1000000007;
LL dp[MAXN][3];
int n,m,k;
LL work(int u,int v)
{
dp[0][0]=dp[0][1]=0;
dp[0][2]=1;
for(int i=1;i<=n;i++)
{
dp[i][2]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%MOD;
if(i<=u) dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%MOD;
else if(i==u+1) dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-1+MOD)%MOD;
else if(i>u+1) dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-dp[i-u-1][1]-dp[i-u-1][2]+MOD)%MOD;
if(i<=v) dp[i][1]=(dp[i-1][1]+dp[i-1][0]+dp[i-1][2])%MOD;
else if(i==v+1) dp[i][1]=(dp[i-1][1]+dp[i-1][0]+dp[i-1][2]-1+MOD)%MOD;
else if(i>v+1) dp[i][1]=(dp[i-1][1]+dp[i-1][0]+dp[i-1][2]-dp[i-v-1][0]-dp[i-v-1][2]+MOD)%MOD;
}
return (dp[n][0]+dp[n][1]+dp[n][2])%MOD;
}
int main()
{
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
printf("%lld\n",((work(n,k)-work(m-1,k))%MOD+MOD)%MOD);
return 0;
}
Coin Toss
题意;
长度为ｎ的字符串仅由Ｈ和Ｔ组成，求出至少包括ｋ个连续的Ｈ的长度为ｎ字符串的总数
题解:
同上；因为求出总数比较大，所以用java大数
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
private static BigInteger dp[][]=new BigInteger[110][2];
private static BigInteger work(int n,int k)
{
dp[0][0]=new BigInteger("0");
dp[0][1]=new BigInteger("1");
for(int i=1;i<=n;i++)
{
dp[i][1]=dp[i-1][1].add(dp[i-1][0]);
if(i<=k) dp[i][0]=dp[i-1][0].add(dp[i-1][1]);
else if(i+1==k) dp[i][0]=dp[i-1][0].add(dp[i-1][1]).subtract(BigInteger.ONE);
else if(i>k) dp[i][0]=dp[i-1][0].add(dp[i-1][1]).subtract(dp[i-k-1][1]);
}
return dp[n][0].add(dp[n][1]);
}
public static void main(String[] args) {
int n,k;
Scanner in=new Scanner(System.in);
while(in.hasNextInt())
{
n=in.nextInt();
k=in.nextInt();
System.out.println(work(n,n).subtract(work(n,k-1)));
}
}
}
Mex
占坑占坑
占坑占坑
占坑占坑
占坑占坑
The King’s Ups and Downs
题意:
有n个身高不一样的士兵,求出身高呈现波浪状(高低高或高低)的排列数
题解:
假设前面n-1个人已经排好,那么对于第n个人来讲,他一定是最高的,所以他插入到队伍中,前面那段的结尾一定是由高到低,后面那段的开头一定是低到高;如果知道前面结尾高低的方法数n和后面开始低高的方法数m。那么在该位置的方法数就为n*m;假设dp[i][0]表示有i个人且结尾是高低的方法数,dp[i][1]表示有i个人且开头是底高的方法数,我们枚举前面的长度j [0,i-1],那么方法数ans[i]+=dp[j][0]*dp[i-j-1][1]*C[i-1][j];c[i-1][j]为组合数,因为从i-1个数字选出j个放到前面;由于镜像的关系,dp[i][0]=dp[i][1]=ans[i]/2;
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=25;
long long dp[25][2];
long long cal[25][25];
long long ans[25];
int main()
{
for(int i=0;i<21;i++)
{
cal[i][0]=1;
for(int j=1;j<i;j++)
{
cal[i][j]=cal[i-1][j]+cal[i-1][j-1];
}
cal[i][i]=1;
}
dp[0][0]=1;
dp[0][1]=1;
dp[1][0]=1;
dp[1][1]=1;
memset(ans,0,sizeof(ans));
ans[1]=1;
for(int i=2;i<21;i++)
{
for(int j=0;j<i;j++)//枚举前面的长度
{
ans[i]+=dp[j][0]*dp[i-j-1][1]*cal[i-1][j];
}
dp[i][0]=dp[i][1]=ans[i]/2;
}
int t;
scanf("%d",&t);
int cas,n;
while(t--)
{
scanf("%d%d",&cas,&n);
printf("%d %lld\n",cas,ans[n]);
}
return 0;
}
Number String
题意:
输入一串由'I','D','?'组成的长度为n的字符串;'I'表示前一个数字和当前数字是升序关系,'D'表示前一个数字和当前数字是降序关系,'?'表示任意顺序;比如排列 {3, 1, 2, 7, 4, 6, 5} 表示为字符串 DIIDID。
计算所有能产生给定字符串的序列数量，每个序列含n+1个数字，分别为1～n+1，即从1开始且不重复。
题解:
因为dp[i]的第一维是1-i的排列的方案,为了体现大小关系,第二维应为数值;
假设dp[i][j]表示前i个满足字符串条件的结尾为j的 i 的排列，注意是i的排列，前面并没有数大于i;
如果s[i - 1]是' I '，那么dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + .. + dp[i-1][1]
可进一步简化，dp[i][j] = dp[i][j-1]+dp[i-1][j-1]
如果s[i - 1]是‘D’，那么dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + ... + dp[i-1][i-1]
可进一步简化，dp[i][j] = dp[i-1][j+1]+dp[i-1][j]
因为要令当前位为j，如果前面出现过j，就令前面的所有大于等于j的数+1，就能构造出新的排列了。比如
{1, 3, 5, 2, 4}，要在第六位插入3,令 >= 3的数都+1，于是就构造出新的排列{1, 4, 6, 2, 5, 3}。
#include<cstdio>
#include<cstring>
using namespace std;
const int MOD=1000000007;
const int MAXN=1010;
char str[MAXN];
int dp[MAXN][MAXN];
int main()
{
while(scanf("%s",str+1)!=EOF)
{
int len=strlen(str+1);
memset(dp,0,sizeof(dp));
dp[1][1]=1;
for(int i=2;i<=len+1;i++)
{
if(str[i-1]=='I')
{
for(int j=2;j<=i;j++)
{
dp[i][j]=(dp[i][j-1]+dp[i-1][j-1])%MOD;
}
}
else if(str[i-1]=='D')
{
for(int j=i-1;j>=1;j--)
{
dp[i][j]=(dp[i][j+1]+dp[i-1][j])%MOD;
}
}
else
{
int sum=0;
for(int j=1;j<=i-1;j++)
{
sum=(sum+dp[i-1][j])%MOD;
}
for(int j=1;j<=i;j++)
{
dp[i][j]=sum;
}
}
}
int ans=0;
for(int i=1;i<=len+1;i++)
{
ans=(ans+dp[len+1][i])%MOD;
}
printf("%d\n",ans);
}
return 0;
}
