ACSL Diff
1 | import java.util.Scanner; |
1 | import java.util.Scanner; |
1 | import java.util.Scanner; |
1 | import java.util.Scanner; |
Nothing… The problem is pretty easy, however it troubled me for a quite long time. Just follow the instruction of the problem and simulate the whole process by coding.
String
and int
carry
sign
char
to simplify the process当然还有另外一种思路(*太强了!!!*):
1 | int f[N][N],mp[N][N]; |
f[i][j][k][l]f[i][j][k][l]表示现在去的到了(i,j),回来的到了(k,l)
一共有四种情况,上上,左左,上左,左上
保证两条路径不相交if(j1==j2 && i1==i2) continue
f[i][j][k][l]=max(f[i−1][j][k−1])f[i][j][k][l]=max(f[i−1][j][k−1])
步数为i+j−1i+j−1
判断不合法的状态
1 | if(i1+j1!=i2+j2) continue; |
当m,n<100m,n<100时,四维数组开不下了,因为i1+j1=i2+j2i1+j1=i2+j2的时候才是合法的,并且三个数都确定时,我们可以直接算出j2j2,直接变成了三维
地面长度为L,高度为H,天上掉馅饼
人在地上每单位时间可以向左或向右移动0~2格,馅饼每单位时间掉落一格
求最多接到多少馅饼(馅饼有分值)
有N种面包,每种面包数量无限多,有高度和价值,高度是5的倍数
将面包叠成一个面包塔,高度不得超过T
给定常数k,若一个面包高度>=k,则它下面所有面包都会被压扁
一个面包最多被压扁一次,它的高度变为原来的4/5
求最大的价值
1 | define N 1e5 |
1 | int f[N][N]; |
课的先修关系形成一棵树的结构,每门课有一门或者没有先修课。选M门课,能获得的最大学分是多少?
在一棵树中选出最多的点,使得这些点中每个点最多与其他点连了k条边
dp[u][0/1][0/1]dp[u][0/1][0/1]表示以u为父亲,取/不取父亲,取/不取自己的最大值
dp[u][0][0]dp[u][0][0]:自己和父亲都不取,u的儿子随便取。$f[u][0][0]=size∑i=1max( dp(vi,0,0) , dp(vi,0,1) )f[u][0][0]=∑i=1sizemax( dp(vi,0,0) , dp(vi,0,1) )$
dp[u][1][0]dp[u][1][0]:父亲要取,u自己不取,u的儿子同样随便取。f[u][1][0]=f[u][0][0]f[u][1][0]=f[u][0][0]
dp[u][1][1]dp[u][1][1]
:父亲要取,自己也要取,儿子取k-1条边。
dp[u][0][1]dp[u][0][1]:父亲不取,自己要取,儿子取k条边