洛谷1437 敲砖块

洛谷1437 敲砖块

原题链接

交题记录

N/A 考试题。。。

题解

先来观察一下性质。

1 1 12 23 

由这个和样例很容易想到这样存储：

1 1 1
2 2
3

即“左对齐”存储。
状态就是\(f[k][i][j]\),表示只在(i,j)和(i,j)上方打最大的收入。
然而并不好转移
的确不好转移。。。。。
呵呵呵
可以无视上面
但如果这样存呢

1
1 2
1 2 3

可以理解为“斜过来”，即：

.//
//
/

再把斜线组成的行看做新行。
现在下面变成了左边。
所以设\(f[i][j][k]\)，在第\(i\)行取前\(j\)个，且一共取了\(k\)个的最大收入
\(f[i][j][k]=max{f[i-1][l][k-j]+s[i][j]}(l=j-1..i-1)\)
即枚举选几个。
注意特判l

Code

// It is made by XZZ
#include
#include
#include
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){rg int x=0,f=1;rg char ch=getchar();while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;
}
int n,m,v[51][51],s[51][51],ss[51],ans=0;
int f[51][51][501];
int main(){
//     #define Fname "brike"// freopen(Fname".in","r",stdin);// freopen(Fname".out","w",stdout);n=gi(),m=gi();rep(j,1,n)drep(i,n,j)v[i][j]=gi();rep(i,1,n)rep(j,1,i)s[i][j]=v[i][j]+s[i][j-1];memset(f,-1,sizeof f);f[0][0][0]=0;rep(i,1,n)rep(j,0,i){rep(k,j,m)rep(l,max(0,j-1),i-1)if(f[i-1][l][k-j]+1)f[i][j][k]=max(f[i][j][k],f[i-1][l][k-j]+s[i][j]);ans=max(ans,f[i][j][m]);}printf("%d\n",ans);return 0;
}

【代码wa了一个点，有人看出来请指正】

转载于:https://www.cnblogs.com/xzz_233/p/7442169.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！