状态题目:[NOI1995]石子合并
题目编号:490-[NOI1995]石子合并 查看该题
状态: Unaccepted
测评机： Xeost[5]
得分： 50分
提交日期： 2009-9-17 18:05:00
有效耗时： 360毫秒
测试结果1: 通过本测试点|有效耗时172ms
测试结果2: 通过本测试点|有效耗时47ms
测试结果3: 通过本测试点|有效耗时47ms
测试结果4: 通过本测试点|有效耗时47ms
测试结果5: 测试结果错误.错误结果为:174
304
正确结果应为:153
304
测试结果6: 通过本测试点|有效耗时47ms
测试结果7: 测试结果错误.错误结果为:275
440
正确结果应为:275
475
测试结果8: 测试结果错误.错误结果为:1289
5025
正确结果应为:1289
5081
测试结果9: 测试结果错误.错误结果为:5915
23692
正确结果应为:5913
24595
测试结果10: 测试结果错误.错误结果为:12554
16054
正确结果应为:12533
95356
提交代码： program stone；
var g:array[0..100,0..100] of integer；
f:array[1..100,1..100] of integer；
s:array[1..100] of integer；
i,j,k,n,min,max:integer；
begin
readln(n)；
for i:=1 to n do read(s[i])；
for i:=1 to n do
for j:=i to n do g[i,j]:=g[i,j-1]+s[j]；
for i:=2 to n do
for j:=1 to n-i+1 do begin
min:=30000；
for k:=j to j+i-2 do
if min>f[j,k]+f[k+1,j+i-1] then
min:=f[j,k]+f[k+1,j+i-1]；
f[j,j+i-1]:=min+g[j,j+i-1]；end；writeln(f[1,n])；
for i:=2 to n do
for j:=1 to n-i+1 do begin
max:=-1；
for k:=j to j+i-2 do
if max<f[j,k]+f[k+1,j+i-1] then
max:=f[j,k]+f[k+1,j+i-1]；
f[j,j+i-1]:=max+g[j,j+i-1]；end；writeln(f[1,n])；
end.
Powered By RenQing | Art Design By Azuis 帮助 关于
鲁ICP备05014231号
Processed in 0.25 second(s).
Copyright (c) 2007-2008 Www.RQNOJ.Cn. All Rights Reserved .
#include<iostream>
using namespace std；
int dp1[200][200]；
int dp2[200][200]；
int stone[200],n；
int sum[200][200]；
void dfs_try1(int l,int r){
if (dp1[l][r]!=-1) return；
if (l==r-1){
dp1[l][r]=0；
return；
}
for (int i=l+1；i<r；++i){
dfs_try1(l,i)；
dfs_try1(i,r)；
dp1[l][r]=max(dp1[l][r],dp1[l][i]+dp1[i][r]+sum[l][r])；
}
}
void dfs_try2(int l,int r){
if (dp2[l][r]!=-1) return；
if (l==r-1){
dp2[l][r]=0；
return；
}
dp2[l][r]=0x7fff；
for (int i=l+1；i<r；++i){
dfs_try2(l,i)；
dfs_try2(i,r)；
dp2[l][r]=min(dp2[l][r],dp2[l][i]+dp2[i][r]+sum[l][r])；
}
}
int main (void){
cin>>n；
for (int i=0；i<n；++i){
cin>>stone[i]；
stone[n+i]=stone[i]；
}
for (int i=0；i<2*n-1；++i)
for (int j=i+1；j<2*n；++j){
sum[i][j]=0；
for (int k=i；k<j；++k) sum[i][j]+=stone[k]；
}
memset(dp1,-1,sizeof(dp1))；
int maxval=0；
for (int i=0；i<n；++i){
dfs_try1(i,i+n)；
maxval=max(maxval,dp1[i][i+n])；
}
memset(dp2,-1,sizeof(dp2))；
int minval=0x7fff；
for (int i=0；i<n；++i){
dfs_try2(i,i+n)；
minval=min(minval,dp2[i][i+n])；
}
cout<<minval<<endl；
cout<<maxval；
return 0；
}
我跟楼主的结果简直是一模一样，只不过我用的C……
代码（请纠错）：
#include"stdio.h"
#define maxn 1001
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
long maxs[maxn][maxn]={0},mins[maxn][maxn],o[maxn][maxn]={0};
long n;
long back(long k)
{
return (k-2+n)%n+1;
}
long liuxk(long k)
{
if(k>n) return k%n;
else return k;
}
int main()
{
memset(mins,0,sizeof(mins));
long i,j;
scanf("%ld",&n);
for(i=1;i<=n;i++)
scanf("%ld",&o[i][i]);
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
o[i][j]=o[i][j-1]+o[j][j];
for(i=1;i<=n;i++)
for(j=1;j<i;j++)
o[i][j]=o[i][back(j)]+o[j][j];
//DP
long L,k;
for(i=1;i<n;i++)
for(j=1;j<=n;j++)
{
L=i+j;
for(k=j;k<L;k++)
{
maxs[j][liuxk(L)]=max(maxs[j][liuxk(L)],maxs[j][liuxk(k)]+maxs[liuxk(k+1)][liuxk(L)]+o[j][liuxk(L)]);
if(mins[j][liuxk(L)]==0)
mins[j][liuxk(L)]=mins[j][liuxk(k)]+mins[liuxk(k+1)][liuxk(L)]+o[j][liuxk(L)];
else
mins[j][liuxk(L)]=min(mins[j][liuxk(L)],mins[j][liuxk(k)]+mins[liuxk(k+1)][liuxk(L)]+o[j][liuxk(L)]);
}
}
printf("%ld\n%ld",mins[1][n],maxs[1][n]);
getchar();getchar();
return 0;
}