1.区间动规 区间动规合并过程
ybt
通过
| 测试点 | 结果 | 内存 | 时间 |
| 测试点1 | 答案正确 | 1708KB | 8MS |
| 测试点2 | 答案正确 | 628KB | 2MS |
| 测试点3 | 答案正确 | 656KB | 2MS |
| 测试点4 | 答案正确 | 764KB | 2MS |
| 测试点5 | 答案正确 | 788KB | 2MS |
| 测试点6 | 答案正确 | 1148KB | 2MS |
| 测试点7 | 答案正确 | 1388KB | 4MS |
| 测试点8 | 答案正确 | 1640KB | 7MS |
| 测试点9 | 答案正确 | 1704KB | 8MS |
| 测试点10 | 答案正确 | 1708KB | 8MS |
LOJ
题意挺玄乎，弄懂样例是关键。
7
1 2 3 4 5 6 7
dp[1][2]=(1+2)*1=2
dp[2][3]=(2+3)*2=10
dp[3][4]=(3+4)*3=21
dp[4][5]=(4+5)*4=36
dp[5][6]=(5+6)*5=55
dp[6][7]=(6+7)*6=78
dp[1][3]=max(dp[2][3]+(1+3)*1,dp[1][2]+(1+3)*2)=max(14,10)=14
dp[2][4]=max(dp[3][4]+(2+4)*2,dp[2][3]+(2+4)*3)=max(33,28)=33
dp[3][5]=max(dp[4][5]+(3+5)*3,dp[3][4]+(3+5)*4)=max(60,53)=60
dp[4][6]=max(dp[5][6]+(4+6)*4,dp[4][5]+(4+6)*5)=max(95,86)=95
dp[5][7]=max(dp[6][7]+(5+7)*5,dp[5][6]+(5+7)*6)=max(138,127)=138
dp[1][4]=max(dp[2][4]+(1+4)*1,dp[1][2]+dp[3][4]+(1+4)*2,dp[1][3]+(1+4)*3)=max(38,33,29)=38
dp[2][5]=max(dp[3][5]+(2+5)*)
dp[3][6]=
dp[4][7]=
dp[1][5]=
dp[2][6]=
dp[3][7]=
dp[1][6]=
dp[2][7]=
dp[1][7]=
实在写不下去了，编码吧，先看看最大值是否能核上。
核验最值及中间过程的代码如下：
#include <bits/stdc++.h>
#define maxn 310
using namespace std;
unsigned int a[maxn],dp[maxn][maxn];
int main(){
int n,lt,rt,k,i,len;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%u",&a[i]);
for(len=1;len<=n-1;len++)
for(lt=1;lt<=n;lt++){
rt=lt+len;
if(rt>n)break;
for(k=0;k<len;k++)
dp[lt][rt]=max(dp[lt][rt],dp[lt][lt+k]+dp[lt+k+1][rt]+(a[lt]+a[rt])*a[lt+k]);
printf("dp[%d][%d]=%u\n",lt,rt,dp[lt][rt]);
}
printf("%u\n",dp[1][n]);
return 0;
}上述代码对应的输入输出数据如下：
7
1 2 3 4 5 6 7
dp[1][2]=3
dp[2][3]=10
dp[3][4]=21
dp[4][5]=36
dp[5][6]=55
dp[6][7]=78
dp[1][3]=14
dp[2][4]=33
dp[3][5]=60
dp[4][6]=95
dp[5][7]=138
dp[1][4]=38
dp[2][5]=74
dp[3][6]=122
dp[4][7]=182
dp[1][5]=80
dp[2][6]=138
dp[3][7]=212
dp[1][6]=145
dp[2][7]=230
dp[1][7]=238
238该题需要记录区间合并过程。
打印区域犯难了，再仔细读题，发现，还是对打印区域进行了具体说明：
例如先打印一分为二的区域，然后从左到右打印二分为四的分离区域，然后是四分为八的……
样例对应的分裂过程如下：
b[1][7]
b[1][1] b[2][7] 输出1
b[1][1] b[2][2] b[3][7] 输出2
b[1][1] b[2][2] b[3][3] b[4][7] 输出3
b[1][1] b[2][2] b[3][3] b[4][4] b[5][7] 输出4
b[1][1] b[2][2] b[3][3] b[4][4] b[5][5] b[6][7] 输出5
b[1][1] b[2][2] b[3][3] b[4][4] b[5][5] b[6][6] b[7][7] 输出6分裂的输出还是比较考验思维的。
基本思路：记录区间动规过程，一遍一遍的打印分裂位置，具体可见代码。
区间动规 区间动规合并过程 代码如下：
#include <bits/stdc++.h>
#define maxn 310
using namespace std;
unsigned int a[maxn],dp[maxn][maxn],b[maxn][maxn],vis[maxn];
int main(){
int n,lt,rt,k,i,len;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%u",&a[i]);
for(len=1;len<=n-1;len++)
for(lt=1;lt<=n;lt++){
rt=lt+len;
if(rt>n)break;
for(k=0;k<len;k++)
if(dp[lt][rt]<dp[lt][lt+k]+dp[lt+k+1][rt]+(a[lt]+a[rt])*a[lt+k]){
dp[lt][rt]=dp[lt][lt+k]+dp[lt+k+1][rt]+(a[lt]+a[rt])*a[lt+k];
b[lt][rt]=lt+k;
}
}
printf("%u\n",dp[1][n]);
int print=1;//打印分裂过程
vis[n]=1;//关键点
while(print){
print=0;
lt=1;
for(rt=1;rt<=n;rt++)
if(vis[rt]){
k=b[lt][rt];
if(k){
printf("%u ",k);
vis[k]=1;
print=1;
}
lt=rt+1;//关键点
}
}
printf("\n");
return 0;
}该题习得了什么？无符号整数的输入与输出。 %u
独立写出了区间动规的分裂过程。