记录信息
评测状态 Accepted
题目 P1202 Selection
递交时间 2015-08-21 22:26:01
代码语言 C++
评测机 VijosEx
消耗时间 185 ms
消耗内存 16220 KiB
评测时间 2015-08-21 22:26:02
评测结果
编译成功

测试数据 #0: Accepted, time = 31 ms, mem = 16216 KiB, score = 20
测试数据 #1: Accepted, time = 46 ms, mem = 16216 KiB, score = 20
测试数据 #2: Accepted, time = 31 ms, mem = 16220 KiB, score = 20
测试数据 #3: Accepted, time = 46 ms, mem = 16216 KiB, score = 20
测试数据 #4: Accepted, time = 31 ms, mem = 16220 KiB, score = 20
Accepted, time = 185 ms, mem = 16220 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
using namespace std;
int f[2002][2002];
int a[2002];
int total[2002];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
total[i]=total[i-1]+a[i];
}
for(int i=1;i<=n;i++)
f[i][i]=a[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j+i<=n;j++)
f[j][j+i]=total[j+i]-total[j-1]-min(f[j+1][j+i],f[j][j+i-1]);
}
if(k==1)
printf("%d",f[1][n]);
else
printf("%d",total[n]-f[1][n]);
}

-3-

1...1

下标写错，过了n遍。。。。经典的动规啊。。。

我觉得好无聊,楼下的一些题解,方程总是要下标省略了.
我很奇怪,既然你不想给大家提供做题经验,那你还写什么题解?是为了秀一下自己有多少牛b?
我不是那种人.
很显然,这道题是一道博弈论.用DP求解即可
f[i,j]表示i-j这个区间里最大的价值。
f[i,j]:=max(a[i]+sum[i+1,j]-f[i+1,j],
a[j]+sum[i,j-1]-f[i,j-1]);
这是比较经典的方程。仔细思考。
DP过后，f数组中存贮的肯定是最优状态。如果是1出手，则答案是f[i,j];相反则是sum[i,j]-f[i,j];

DXE