【BZOJ1084】dp
题目很简单
分析
蛮无聊的一道题。
状态转移十分显然
然后就做完了。
#include <bits/stdc++.h>
#define sc(n) scanf("%d",&n)
#define pt(n) printf("%d\n",n)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
using namespace std;
const int maxn = 110;
int s1[maxn],s2[maxn];
int n,m,k;
int dp[maxn][maxn][maxn];
int main(http://www.my516.com)
{
scanf("%d%d%d",&n,&m,&k);
if(m==1)
{
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
s1[i] = s1[i-1]+x;
}
for(int l=1;l<=k;l++)
{
for(int i=1;i<=n;i++)
{
dp[i][l][0] = dp[i-1][l][0];
for(int j=0;j<i;j++)
{
dp[i][l][0] = max(dp[i][l][0],dp[j][l-1][0]+s1[i]-s1[j]);
}
}
}
printf("%d\n",dp[n][k][0]);
}
else
{
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
s1[i] = s1[i-1]+x;
s2[i] = s2[i-1]+y;
}
for(int l=1;l<=k;l++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j][l] = max(dp[i-1][j][l],dp[i][j-1][l]);
for(int s=0;s<i;s++)
{
dp[i][j][l] = max(dp[i][j][l],dp[s][j][l-1]+s1[i]-s1[s]);
}
for(int s=0;s<j;s++)
{
dp[i][j][l] = max(dp[i][j][l],dp[i][s][l-1]+s2[j]-s2[s]);
}
if(i==j)
{
for(int s=0;s<i;s++)
{
dp[i][j][l] = max(dp[i][j][l],dp[s][s][l-1]+s1[i]-s1[s]+s2[j]-s2[s]);
}
}
}
}
}
printf("%d\n",dp[n][n][k]);
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
---------------------
最新文章
- java 获取中文字符的首字母
- VMware Data Recovery备份恢复vmware虚拟机
- 单调队列应用--BZOJ 3831 Little Bird
- Peer Code Reviews Made Easy with Eclipse Plug-In
- AndroidStudio debug
- Cookies和Sseeion的选择
- (转)委托的N种写法,你喜欢哪种?
- 新手笔记-tftp与yum
- php文件链接数据库基本代码
- spark 中的RDD编程 -以下基于Java api
- Java数据结构和算法(三)——冒泡、选择、插入排序算法
- datatable使用笔记
- mybatis-自定义typeHandler
- Django----模板层
- GWAS:拒绝假阳性之case和control数量比例严重失衡的解决方案(SAIGE模型的应用)
- 解决关于win10下eclipse代码格式化不生效问题
- webpack入门(三)webpack的api
- SW加载标准库时出现failed to create Toolboxlibrary object怎么办?
- crontab挂定时任务
- hdu 5724-Chess(状态压缩+sg函数)