比较一般的dp吧
学lsj教主写了个namespace爽爽
1 #include2 #define lowbit(a) ((a)&(-(a))) 3 #define clr(a,x) memset(a,x,sizeof(a)) 4 #define rep(i,l,r) for(int i=l;i<(r);i++) 5 typedef long long ll; 6 using namespace std; 7 int read() 8 { 9 char c=getchar();10 int ans=0,f=1;11 while(!isdigit(c)){12 if(c=='-') f=-1;13 c=getchar();14 }15 while(isdigit(c)){16 ans=ans*10+c-'0';17 c=getchar();18 }19 return ans*f;20 }21 const int maxn=109,maxm=4,maxk=15;22 int n,m,k;23 namespace one{24 int sum[maxn],d[maxn][maxk];25 void work(){26 clr(sum,0),clr(d,0);27 rep(i,1,n+1){28 int t=read();29 sum[i]=sum[i-1]+t;30 }31 rep(i,1,n+1){32 rep(j,1,k+1){33 d[i][j]=d[i-1][j];34 rep(l,0,i) d[i][j]=max(d[i][j],d[l][j-1]+sum[i]-sum[l]);35 }36 }37 printf("%d\n",d[n][k]);38 }39 }40 namespace two{41 int sum[maxn][maxm],d[maxn][maxn][maxk];42 void work(){43 clr(sum,0),clr(d,0);44 rep(i,1,n+1){45 rep(j,1,m+1){46 int t=read();47 sum[i][j]=sum[i-1][j]+t;48 }49 }50 rep(i,1,n+1){51 rep(j,1,n+1){52 rep(l,1,k+1){53 d[i][j][l]=max(d[i-1][j][l],d[i][j-1][l]);54 rep(p,0,i) d[i][j][l]=max(d[i][j][l],d[p][j][l-1]+sum[i][1]-sum[p][1]);55 rep(p,0,j) d[i][j][l]=max(d[i][j][l],d[i][p][l-1]+sum[j][2]-sum[p][2]);56 if(i==j) rep(p,0,i) d[i][j][l]=max(d[i][j][l],d[p][p][l-1]+sum[i][1]-sum[p][1]+sum[i][2]-sum[p][2]);57 }58 }59 }60 printf("%d\n",d[n][n][k]);61 }62 }63 int main()64 { 65 n=read(),m=read(),k=read();66 m==1?one::work():two::work();67 return 0;68 }
1084: [SCOI2005]最大子矩阵
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1616 Solved: 823[][][]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
Sample Output
9