/*
一道不是很难的动态规划 rp竟然这么高
但是的确很考验思维能力的博弈题
嗯和那个啥P1202有点像(一类)   先去做通P1202
嗯状态是一样的
f[i,j]表示[i,j]中的最大值，但注意只存一个人的
首先需要注意到一个性质：
当确定了哪段[i,j]之后，最后哪个人拿数（i或者j）是确定的，
因此枚举拿i还是拿j，那么哪个更加优呢？
我们可以给每个f[I,j]存一个g[I,j]表示决策，然后往前推k步就行了
即设f[i,j]表示i到j轮到的人能取的最大值
  g[i,j]=1表示取i，g[i,j]=2表示取j那么
f[i,j]=max(a[i]+get(i+1，j),a[j]+get(i,j-1))（倒着取）
get函数是用来求上次此人取得的最大值
即我们可以看到k个人实际上是轮流选择这个最优解的
那么比如第x个人    我们枚举他是取左边还是右边
那我们肯定是要考虑到我们要有
a[i]+(选了a[i]后可以达到的最大值)和a[j]+(选了a[j]后的最大值)要取最大值
那么我们怎么得到选了a[i]或a[j]后可以达到的最大值呢？
我们已经用g[i][j]记录了做[i,j]这个区间决策的时候是选取左边还是右边
所以我们就向前推k-1步  即k-1次取数就是上一轮这个人的时候选取得到的最大值
和1202一样我们的每一个决策都是从一个比它短的区间递推而来
所以我们肯定在[i-1,j]或者[i,j-1]中的所有需要的f[][]和g[][]都已经球出来了
所以我们在[i-1][j]和[i,j-1]中推一遍
仔细考虑这个递推的过程
我们看一直将这个区间缩短    如果g[x][y]==1说明这一个区间最优取的是x
则转换为了[x-1,y]中的问题 x--
同理g[x][y]==2 则y--
那么就有两种情况了，这个人是第一次选数字    那么肯定推不到他上次选数的情况
就会出现x>y了    如果没有出现这种情况  那么我们在循环k-1次后
得到的新的f[x][y]一定就是他上次选数之后的最优解了
所以我们就可以根据情况返回0或者f[x][y]
这个函数很重要考虑到了一种DP递推的思路
至于输出答案
我们就按照f[][]和g[][]走一遍
当走完k个人的时候   肯定就将每个人的最优解得出来了
好题  锻炼思维了
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1002;
int a[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int n,k;

void init()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i],g[i][i]=1,f[i][i]=a[i];
}

int get(int x,int y)//求上次此人取得的最大和
{
    for(int i=1;i<=k-1;i++)
        if(x>y)
            break;
        else    if(g[x][y]==1)
            x++;
        else
            y--;
    if(x<=y)   
        return f[x][y];
    else
        return 0;
}

void getans()
{
    int x=1;    int y=n;
    for(int i=1;i<=k;i++)
    {
        cout<<f[x][y]<<endl;
        if(g[x][y]==1)
            x++;
        else
            y--;
    }
}

int main()
{
    init();
    for(int l=1;l<=n-1;l++)//长度
        for(int i=1;i<=n-l;i++)//起点
        {
            int j=i+l;//终点
            int x=get(i+1,j);//求出上次
            int y=get(i,j-1);//的最大值
            if(x+a[i]>y+a[j])
            {
                f[i][j]=x+a[i];
                g[i][j]=1;
            }
            else
            {
                f[i][j]=y+a[j];
                g[i][j]=2;
            }
        }
    getans();
    return 0;
}
     

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / Advanced Selection /
题解
27 条题解
0
real_hdsy_gyz LV 0
发表您的题解
2

PowderHan LV 10 @ 4 年前
/*
一道不是很难的动态规划 rp竟然这么高
但是的确很考验思维能力的博弈题
嗯和那个啥P1202有点像(一类) 先去做通P1202
嗯状态是一样的
f[i,j]表示[i,j]中的最大值，但注意只存一个人的
首先需要注意到一个性质：
当确定了哪段[i,j]之后，最后哪个人拿数（i或者j）是确定的，
因此枚举拿i还是拿j，那么哪个更加优呢？
我们可以给每个f[I,j]存一个g[I,j]表示决策，然后往前推k步就行了
即设f[i,j]表示i到j轮到的人能取的最大值
g[i,j]=1表示取i，g[i,j]=2表示取j那么
f[i,j]=max(a[i]+get(i+1，j),a[j]+get(i,j-1))（倒着取）
get函数是用来求上次此人取得的最大值
即我们可以看到k个人实际上是轮流选择这个最优解的
那么比如第x个人 我们枚举他是取左边还是右边
那我们肯定是要考虑到我们要有
a[i]+(选了a[i]后可以达到的最大值)和a[j]+(选了a[j]后的最大值)要取最大值
那么我们怎么得到选了a[i]或a[j]后可以达到的最大值呢？
我们已经用g[i][j]记录了做[i,j]这个区间决策的时候是选取左边还是右边
所以我们就向前推k-1步 即k-1次取数就是上一轮这个人的时候选取得到的最大值
和1202一样我们的每一个决策都是从一个比它短的区间递推而来
所以我们肯定在[i-1,j]或者[i,j-1]中的所有需要的f[][]和g[][]都已经球出来了
所以我们在[i-1][j]和[i,j-1]中推一遍
仔细考虑这个递推的过程
我们看一直将这个区间缩短 如果g[x][y]==1说明这一个区间最优取的是x
则转换为了[x-1,y]中的问题 x--
同理g[x][y]==2 则y--
那么就有两种情况了，这个人是第一次选数字 那么肯定推不到他上次选数的情况
就会出现x>y了 如果没有出现这种情况 那么我们在循环k-1次后
得到的新的f[x][y]一定就是他上次选数之后的最优解了
所以我们就可以根据情况返回0或者f[x][y]
这个函数很重要考虑到了一种DP递推的思路
至于输出答案
我们就按照f[][]和g[][]走一遍
当走完k个人的时候 肯定就将每个人的最优解得出来了
好题 锻炼思维了
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1002;
int a[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int n,k;

void init()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],g[i][i]=1,f[i][i]=a[i];
}

int get(int x,int y)//求上次此人取得的最大和
{
for(int i=1;i<=k-1;i++)
if(x>y)
break;
else if(g[x][y]==1)
x++;
else
y--;
if(x<=y)

return f[x][y];
else
return 0;
}

void getans()
{
int x=1; int y=n;
for(int i=1;i<=k;i++)
{
cout<<f[x][y]<<endl;
if(g[x][y]==1)
x++;
else
y--;
}
}

int main()
{
init();
for(int l=1;l<=n-1;l++)//长度
for(int i=1;i<=n-l;i++)//起点
{
int j=i+l;//终点
int x=get(i+1,j);//求出上次
int y=get(i,j-1);//的最大值
if(x+a[i]>y+a[j])
{
f[i][j]=x+a[i];
g[i][j]=1;
}
else
{
f[i][j]=y+a[j];
g[i][j]=2;
}
}
getans();
return 0;
}

Copy
0

real_hdsy_gyz LV 0 @ 刚刚

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / Advanced Selection /
题解
26 条题解
0
real_hdsy_gyz LV 0
发表您的题解
2

PowderHan LV 10 @ 4 年前
/*
一道不是很难的动态规划 rp竟然这么高
但是的确很考验思维能力的博弈题
嗯和那个啥P1202有点像(一类) 先去做通P1202
嗯状态是一样的
f[i,j]表示[i,j]中的最大值，但注意只存一个人的
首先需要注意到一个性质：
当确定了哪段[i,j]之后，最后哪个人拿数（i或者j）是确定的，
因此枚举拿i还是拿j，那么哪个更加优呢？
我们可以给每个f[I,j]存一个g[I,j]表示决策，然后往前推k步就行了
即设f[i,j]表示i到j轮到的人能取的最大值
g[i,j]=1表示取i，g[i,j]=2表示取j那么
f[i,j]=max(a[i]+get(i+1，j),a[j]+get(i,j-1))（倒着取）
get函数是用来求上次此人取得的最大值
即我们可以看到k个人实际上是轮流选择这个最优解的
那么比如第x个人 我们枚举他是取左边还是右边
那我们肯定是要考虑到我们要有
a[i]+(选了a[i]后可以达到的最大值)和a[j]+(选了a[j]后的最大值)要取最大值
那么我们怎么得到选了a[i]或a[j]后可以达到的最大值呢？
我们已经用g[i][j]记录了做[i,j]这个区间决策的时候是选取左边还是右边
所以我们就向前推k-1步 即k-1次取数就是上一轮这个人的时候选取得到的最大值
和1202一样我们的每一个决策都是从一个比它短的区间递推而来
所以我们肯定在[i-1,j]或者[i,j-1]中的所有需要的f[][]和g[][]都已经球出来了
所以我们在[i-1][j]和[i,j-1]中推一遍
仔细考虑这个递推的过程
我们看一直将这个区间缩短 如果g[x][y]==1说明这一个区间最优取的是x
则转换为了[x-1,y]中的问题 x--
同理g[x][y]==2 则y--
那么就有两种情况了，这个人是第一次选数字 那么肯定推不到他上次选数的情况
就会出现x>y了 如果没有出现这种情况 那么我们在循环k-1次后
得到的新的f[x][y]一定就是他上次选数之后的最优解了
所以我们就可以根据情况返回0或者f[x][y]
这个函数很重要考虑到了一种DP递推的思路
至于输出答案
我们就按照f[][]和g[][]走一遍
当走完k个人的时候 肯定就将每个人的最优解得出来了
好题 锻炼思维了
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1002;
int a[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int n,k;

void init()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],g[i][i]=1,f[i][i]=a[i];
}

int get(int x,int y)//求上次此人取得的最大和
{
for(int i=1;i<=k-1;i++)
if(x>y)
break;
else if(g[x][y]==1)
x++;
else
y--;
if(x<=y)

return f[x][y];
else
return 0;
}

void getans()
{
int x=1; int y=n;
for(int i=1;i<=k;i++)
{
cout<<f[x][y]<<endl;
if(g[x][y]==1)
x++;
else
y--;
}
}

int main()
{
init();
for(int l=1;l<=n-1;l++)//长度
for(int i=1;i<=n-l;i++)//起点
{
int j=i+l;//终点
int x=get(i+1,j);//求出上次
int y=get(i,j-1);//的最大值
if(x+a[i]>y+a[j])
{
f[i][j]=x+a[i];
g[i][j]=1;
}
else
{
f[i][j]=y+a[j];
g[i][j]=2;
}
}
getans();
return 0;
}

Copy
0

real_hdsy_gyz LV 0 @ 刚刚

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / Advanced Selection /
题解
25 条题解
0
real_hdsy_gyz LV 0
发表您的题解
2

PowderHan LV 10 @ 4 年前
/*
一道不是很难的动态规划 rp竟然这么高
但是的确很考验思维能力的博弈题
嗯和那个啥P1202有点像(一类) 先去做通P1202
嗯状态是一样的
f[i,j]表示[i,j]中的最大值，但注意只存一个人的
首先需要注意到一个性质：
当确定了哪段[i,j]之后，最后哪个人拿数（i或者j）是确定的，
因此枚举拿i还是拿j，那么哪个更加优呢？
我们可以给每个f[I,j]存一个g[I,j]表示决策，然后往前推k步就行了
即设f[i,j]表示i到j轮到的人能取的最大值
g[i,j]=1表示取i，g[i,j]=2表示取j那么
f[i,j]=max(a[i]+get(i+1，j),a[j]+get(i,j-1))（倒着取）
get函数是用来求上次此人取得的最大值
即我们可以看到k个人实际上是轮流选择这个最优解的
那么比如第x个人 我们枚举他是取左边还是右边
那我们肯定是要考虑到我们要有
a[i]+(选了a[i]后可以达到的最大值)和a[j]+(选了a[j]后的最大值)要取最大值
那么我们怎么得到选了a[i]或a[j]后可以达到的最大值呢？
我们已经用g[i][j]记录了做[i,j]这个区间决策的时候是选取左边还是右边
所以我们就向前推k-1步 即k-1次取数就是上一轮这个人的时候选取得到的最大值
和1202一样我们的每一个决策都是从一个比它短的区间递推而来
所以我们肯定在[i-1,j]或者[i,j-1]中的所有需要的f[][]和g[][]都已经球出来了
所以我们在[i-1][j]和[i,j-1]中推一遍
仔细考虑这个递推的过程
我们看一直将这个区间缩短 如果g[x][y]==1说明这一个区间最优取的是x
则转换为了[x-1,y]中的问题 x--
同理g[x][y]==2 则y--
那么就有两种情况了，这个人是第一次选数字 那么肯定推不到他上次选数的情况
就会出现x>y了 如果没有出现这种情况 那么我们在循环k-1次后
得到的新的f[x][y]一定就是他上次选数之后的最优解了
所以我们就可以根据情况返回0或者f[x][y]
这个函数很重要考虑到了一种DP递推的思路
至于输出答案
我们就按照f[][]和g[][]走一遍
当走完k个人的时候 肯定就将每个人的最优解得出来了
好题 锻炼思维了
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1002;
int a[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int n,k;

void init()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],g[i][i]=1,f[i][i]=a[i];
}

int get(int x,int y)//求上次此人取得的最大和
{
for(int i=1;i<=k-1;i++)
if(x>y)
break;
else if(g[x][y]==1)
x++;
else
y--;
if(x<=y)

return f[x][y];
else
return 0;
}

void getans()
{
int x=1; int y=n;
for(int i=1;i<=k;i++)
{
cout<<f[x][y]<<endl;
if(g[x][y]==1)
x++;
else
y--;
}
}

int main()
{
init();
for(int l=1;l<=n-1;l++)//长度
for(int i=1;i<=n-l;i++)//起点
{
int j=i+l;//终点
int x=get(i+1,j);//求出上次
int y=get(i,j-1);//的最大值
if(x+a[i]>y+a[j])
{
f[i][j]=x+a[i];
g[i][j]=1;
}
else
{
f[i][j]=y+a[j];
g[i][j]=2;
}
}
getans();
return 0;
}

Copy
0

real_hdsy_gyz LV 0 @ 26 秒前

艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / Advanced Selection /
题解
24 条题解
0
real_hdsy_gyz LV 0
艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
​

​
​
​
​

2

PowderHan LV 10 @ 4 年前
/*
一道不是很难的动态规划 rp竟然这么高
但是的确很考验思维能力的博弈题
嗯和那个啥P1202有点像(一类) 先去做通P1202
嗯状态是一样的
f[i,j]表示[i,j]中的最大值，但注意只存一个人的
首先需要注意到一个性质：
当确定了哪段[i,j]之后，最后哪个人拿数（i或者j）是确定的，
因此枚举拿i还是拿j，那么哪个更加优呢？
我们可以给每个f[I,j]存一个g[I,j]表示决策，然后往前推k步就行了
即设f[i,j]表示i到j轮到的人能取的最大值
g[i,j]=1表示取i，g[i,j]=2表示取j那么
f[i,j]=max(a[i]+get(i+1，j),a[j]+get(i,j-1))（倒着取）
get函数是用来求上次此人取得的最大值
即我们可以看到k个人实际上是轮流选择这个最优解的
那么比如第x个人 我们枚举他是取左边还是右边
那我们肯定是要考虑到我们要有
a[i]+(选了a[i]后可以达到的最大值)和a[j]+(选了a[j]后的最大值)要取最大值
那么我们怎么得到选了a[i]或a[j]后可以达到的最大值呢？
我们已经用g[i][j]记录了做[i,j]这个区间决策的时候是选取左边还是右边
所以我们就向前推k-1步 即k-1次取数就是上一轮这个人的时候选取得到的最大值
和1202一样我们的每一个决策都是从一个比它短的区间递推而来
所以我们肯定在[i-1,j]或者[i,j-1]中的所有需要的f[][]和g[][]都已经球出来了
所以我们在[i-1][j]和[i,j-1]中推一遍
仔细考虑这个递推的过程
我们看一直将这个区间缩短 如果g[x][y]==1说明这一个区间最优取的是x
则转换为了[x-1,y]中的问题 x--
同理g[x][y]==2 则y--
那么就有两种情况了，这个人是第一次选数字 那么肯定推不到他上次选数的情况
就会出现x>y了 如果没有出现这种情况 那么我们在循环k-1次后
得到的新的f[x][y]一定就是他上次选数之后的最优解了
所以我们就可以根据情况返回0或者f[x][y]
这个函数很重要考虑到了一种DP递推的思路
至于输出答案
我们就按照f[][]和g[][]走一遍
当走完k个人的时候 肯定就将每个人的最优解得出来了
好题 锻炼思维了
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1002;
int a[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int n,k;

void init()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],g[i][i]=1,f[i][i]=a[i];
}

int get(int x,int y)//求上次此人取得的最大和
{
for(int i=1;i<=k-1;i++)
if(x>y)
break;
else if(g[x][y]==1)
x++;
else
y--;
if(x<=y)

return f[x][y];
else
return 0;
}

void getans()
{
int x=1; int y=n;
for(int i=1;i<=k;i++)
{
cout<<f[x][y]<<endl;
if(g[x][y]==1)
x++;
else
y--;
}
}

int main()
{
init();
for(int l=1;l<=n-1;l++)//长度
for(int i=1;i<=n-l;i++)//起点
{
int j=i+l;//终点
int x=get(i+1,j);//求出上次
int y=get(i,j-1);//的最大值
if(x+a[i]>y+a[j])
{
f[i][j]=x+a[i];
g[i][j]=1;
}
else
{
f[i][j]=y+a[j];
g[i][j]=2;
}
}
getans();
return 0;
}

Copy
0

ljt12138 LV 10 @ 5 年前
还是挺有意思的一道题。
用dp做敌对搜索的思路很巧妙！

0

prince_hao LV 10 @ 11 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

第一次忘记限制下标了结果是WA...

0

voyagec2 LV 10 @ 12 年前
原来如此..

0

ShingRay LV 10 @ 12 年前
opt[i][j] 表示对于 i~j，当前面临选择的同学最大取得的和

有两种选法，选 i 和选 j

pre[i][j]: 面临 i~j 时最优选择方案， 0:选i；1:选j

若选 i

x, y, kk = i+1, j, k-1

while kk > 0:

__|_if pre[x][y] == 0: x += 1

__|_else: y -= 1

___|_kk -= 1

return opt[x][y] + a[i]

选 j 类似

0

jacklv LV 10 @ 12 年前
这题虽然破百了，但是我认为还是值得一写（后悔当初99人的时候没挤一下）

先倒着动规求出f表示某个人取时可以取到的最大值。这个时候还是要做个函数比较方便吧，这个状态是和它倒退k-1步有关的，因为别人还要取。用g表示在面对i到j的数列时取i则g=1 else g=2 ，g的处理对倒退k-1步和最后求每个人取到的数也是有关的

t1=back(i+1,j); t2=back(i,j-1);

if t1+a[i]>t2+a[j] then

begin

f=t1+a[i];

g:=1;

end else ...

最后对于每个人若是他的回合，他面对的数列是i~j

则用g去判断他是取i优还是取j优

总的算法复杂度是（n*n*k）吧

还是过的去的

0

yzl609271536 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 494ms

├ 测试数据 02：答案正确... 447ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1538ms

第100个

这题应该归到DP

0

陈亮宇 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 711ms

├ 测试数据 02：答案正确... 618ms

├ 测试数据 03：答案正确... 306ms

├ 测试数据 04：答案正确... 508ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2143ms

啊蛤蛤 虽然 时间比较慢

此题 第99个AC 的人~

~ AC ~ 100 ~ 题庆

100/321(31%) 　

通过 　　99人

调试了好久 原来是动态规划 。。。 枚举边界问题啊！

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 338ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1116ms

e开头的那个评测机

好了些

0

TLD LV 10 @ 12 年前
其实用个结构体做个返回值就可以了

0

怪盗~基德 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

这时间还真不爽，动规题就该秒杀的。。。。。。

0

mike_nzk LV 10 @ 12 年前
这种沙茶题还3次AC...太弱了...

0

LV 0 @ 12 年前
大牛说的没错，因为每次都保留了决策，做的时候往前推k-1步就知道取i优还是取j优了。

贴下主过程～

但我这样做暴慢～～～，再推k步(back函数）的时候能否优化呢？

for l:=2 to n do

begin

for i:=1 to n-l+1 do

begin

j:=i+l-1;

k1:=back(i+1,j);

k2:=back(i,j-1);

if k1+p[i]>k2+p[j] then begin

f:=k1+p[i];

g:=1;

end

else begin

f:=k2+p[j];

g:=2;

end;

end;

end;

0

k103701 LV 10 @ 13 年前
编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

一个地方改了3遍,从p

0

notblack LV 10 @ 13 年前
样例有什么意义..............

0

junlonely LV 7 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜whqlsc牛牛。！~

0

dengailing LV 3 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多亏了楼上的牛啊。。。。。。。。。。。。。。。

清哥加油！！！！！！！！~~~~~~~~~~~~~~~~

0

FancyMouse LV 3 @ 14 年前
记录状态转移的时候只能逆推（因为某个状态顺推可能有两解）

补充一句……case4我有理由怀疑输入数据少了一个数。即in文件里只有999个数。

大多数人都把变量设为全局变量，因此默认为0——这也是标程默认的，因此以前没人发现这个问题- -

所以，如果是把数据输入局部变量的话，请不要忘记清0。。。

0

zyz915 LV 8 @ 14 年前
唔,总算,想了好久的DP啊...

0

gamejifan LV 7 @ 15 年前
本人主要功绩就是把这题通过率拉下来一个百分点。

我靠。。我只不过DP的时候用了它80MB的内存就说我溢出了，害得我只能用滚动数组

0

thebeet LV 3 @ 15 年前
此题其实和１２０２差不多．．．

做决策的时候　就是多往前面推K步

1 2 下一页 › 末页 »
Advanced Selection
查看题目
递交
讨论
题解
信息
ID1207递交 Accepted难度4分类点击显示标签(无)递交数197我的递交数1已通过79通过率40%被复制3上传者 lolanv
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

0

ljt12138 LV 10 @ 5 年前
还是挺有意思的一道题。
用dp做敌对搜索的思路很巧妙！

0

prince_hao LV 10 @ 11 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

第一次忘记限制下标了结果是WA...

0

voyagec2 LV 10 @ 12 年前
原来如此..

0

ShingRay LV 10 @ 12 年前
opt[i][j] 表示对于 i~j，当前面临选择的同学最大取得的和

有两种选法，选 i 和选 j

pre[i][j]: 面临 i~j 时最优选择方案， 0:选i；1:选j

若选 i

x, y, kk = i+1, j, k-1

while kk > 0:

__|_if pre[x][y] == 0: x += 1

__|_else: y -= 1

___|_kk -= 1

return opt[x][y] + a[i]

选 j 类似

0

jacklv LV 10 @ 12 年前
这题虽然破百了，但是我认为还是值得一写（后悔当初99人的时候没挤一下）

先倒着动规求出f表示某个人取时可以取到的最大值。这个时候还是要做个函数比较方便吧，这个状态是和它倒退k-1步有关的，因为别人还要取。用g表示在面对i到j的数列时取i则g=1 else g=2 ，g的处理对倒退k-1步和最后求每个人取到的数也是有关的

t1=back(i+1,j); t2=back(i,j-1);

if t1+a[i]>t2+a[j] then

begin

f=t1+a[i];

g:=1;

end else ...

最后对于每个人若是他的回合，他面对的数列是i~j

则用g去判断他是取i优还是取j优

总的算法复杂度是（n*n*k）吧

还是过的去的

0

yzl609271536 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 494ms

├ 测试数据 02：答案正确... 447ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1538ms

第100个

这题应该归到DP

0

陈亮宇 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 711ms

├ 测试数据 02：答案正确... 618ms

├ 测试数据 03：答案正确... 306ms

├ 测试数据 04：答案正确... 508ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2143ms

啊蛤蛤 虽然 时间比较慢

此题 第99个AC 的人~

~ AC ~ 100 ~ 题庆

100/321(31%) 　

通过 　　99人

调试了好久 原来是动态规划 。。。 枚举边界问题啊！

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 338ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1116ms

e开头的那个评测机

好了些

0

TLD LV 10 @ 12 年前
其实用个结构体做个返回值就可以了

0

怪盗~基德 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

这时间还真不爽，动规题就该秒杀的。。。。。。

0

mike_nzk LV 10 @ 12 年前
这种沙茶题还3次AC...太弱了...

0

LV 0 @ 12 年前
大牛说的没错，因为每次都保留了决策，做的时候往前推k-1步就知道取i优还是取j优了。

贴下主过程～

但我这样做暴慢～～～，再推k步(back函数）的时候能否优化呢？

for l:=2 to n do

begin

for i:=1 to n-l+1 do

begin

j:=i+l-1;

k1:=back(i+1,j);

k2:=back(i,j-1);

if k1+p[i]>k2+p[j] then begin

f:=k1+p[i];

g:=1;

end

else begin

f:=k2+p[j];

g:=2;

end;

end;

end;

0

k103701 LV 10 @ 13 年前
编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

一个地方改了3遍,从p

0

notblack LV 10 @ 13 年前
样例有什么意义..............

0

junlonely LV 7 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜whqlsc牛牛。！~

0

dengailing LV 3 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多亏了楼上的牛啊。。。。。。。。。。。。。。。

清哥加油！！！！！！！！~~~~~~~~~~~~~~~~

0

FancyMouse LV 3 @ 14 年前
记录状态转移的时候只能逆推（因为某个状态顺推可能有两解）

补充一句……case4我有理由怀疑输入数据少了一个数。即in文件里只有999个数。

大多数人都把变量设为全局变量，因此默认为0——这也是标程默认的，因此以前没人发现这个问题- -

所以，如果是把数据输入局部变量的话，请不要忘记清0。。。

0

zyz915 LV 8 @ 14 年前
唔,总算,想了好久的DP啊...

0

gamejifan LV 7 @ 15 年前
本人主要功绩就是把这题通过率拉下来一个百分点。

我靠。。我只不过DP的时候用了它80MB的内存就说我溢出了，害得我只能用滚动数组

1 2 下一页 › 末页 »
Advanced Selection
查看题目
递交
讨论
题解
信息
ID1207递交 Accepted难度4分类点击显示标签(无)递交数197我的递交数1已通过79通过率40%被复制3上传者 lolanv
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

0

real_hdsy_gyz LV 0 @ 32 秒前

艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / Advanced Selection /
题解
24 条题解
0
real_hdsy_gyz LV 0
艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
​

​
​
​
​

2

PowderHan LV 10 @ 4 年前
/*
一道不是很难的动态规划 rp竟然这么高
但是的确很考验思维能力的博弈题
嗯和那个啥P1202有点像(一类) 先去做通P1202
嗯状态是一样的
f[i,j]表示[i,j]中的最大值，但注意只存一个人的
首先需要注意到一个性质：
当确定了哪段[i,j]之后，最后哪个人拿数（i或者j）是确定的，
因此枚举拿i还是拿j，那么哪个更加优呢？
我们可以给每个f[I,j]存一个g[I,j]表示决策，然后往前推k步就行了
即设f[i,j]表示i到j轮到的人能取的最大值
g[i,j]=1表示取i，g[i,j]=2表示取j那么
f[i,j]=max(a[i]+get(i+1，j),a[j]+get(i,j-1))（倒着取）
get函数是用来求上次此人取得的最大值
即我们可以看到k个人实际上是轮流选择这个最优解的
那么比如第x个人 我们枚举他是取左边还是右边
那我们肯定是要考虑到我们要有
a[i]+(选了a[i]后可以达到的最大值)和a[j]+(选了a[j]后的最大值)要取最大值
那么我们怎么得到选了a[i]或a[j]后可以达到的最大值呢？
我们已经用g[i][j]记录了做[i,j]这个区间决策的时候是选取左边还是右边
所以我们就向前推k-1步 即k-1次取数就是上一轮这个人的时候选取得到的最大值
和1202一样我们的每一个决策都是从一个比它短的区间递推而来
所以我们肯定在[i-1,j]或者[i,j-1]中的所有需要的f[][]和g[][]都已经球出来了
所以我们在[i-1][j]和[i,j-1]中推一遍
仔细考虑这个递推的过程
我们看一直将这个区间缩短 如果g[x][y]==1说明这一个区间最优取的是x
则转换为了[x-1,y]中的问题 x--
同理g[x][y]==2 则y--
那么就有两种情况了，这个人是第一次选数字 那么肯定推不到他上次选数的情况
就会出现x>y了 如果没有出现这种情况 那么我们在循环k-1次后
得到的新的f[x][y]一定就是他上次选数之后的最优解了
所以我们就可以根据情况返回0或者f[x][y]
这个函数很重要考虑到了一种DP递推的思路
至于输出答案
我们就按照f[][]和g[][]走一遍
当走完k个人的时候 肯定就将每个人的最优解得出来了
好题 锻炼思维了
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1002;
int a[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int n,k;

void init()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],g[i][i]=1,f[i][i]=a[i];
}

int get(int x,int y)//求上次此人取得的最大和
{
for(int i=1;i<=k-1;i++)
if(x>y)
break;
else if(g[x][y]==1)
x++;
else
y--;
if(x<=y)

return f[x][y];
else
return 0;
}

void getans()
{
int x=1; int y=n;
for(int i=1;i<=k;i++)
{
cout<<f[x][y]<<endl;
if(g[x][y]==1)
x++;
else
y--;
}
}

int main()
{
init();
for(int l=1;l<=n-1;l++)//长度
for(int i=1;i<=n-l;i++)//起点
{
int j=i+l;//终点
int x=get(i+1,j);//求出上次
int y=get(i,j-1);//的最大值
if(x+a[i]>y+a[j])
{
f[i][j]=x+a[i];
g[i][j]=1;
}
else
{
f[i][j]=y+a[j];
g[i][j]=2;
}
}
getans();
return 0;
}

Copy
0

ljt12138 LV 10 @ 5 年前
还是挺有意思的一道题。
用dp做敌对搜索的思路很巧妙！

0

prince_hao LV 10 @ 11 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

第一次忘记限制下标了结果是WA...

0

voyagec2 LV 10 @ 12 年前
原来如此..

0

ShingRay LV 10 @ 12 年前
opt[i][j] 表示对于 i~j，当前面临选择的同学最大取得的和

有两种选法，选 i 和选 j

pre[i][j]: 面临 i~j 时最优选择方案， 0:选i；1:选j

若选 i

x, y, kk = i+1, j, k-1

while kk > 0:

__|_if pre[x][y] == 0: x += 1

__|_else: y -= 1

___|_kk -= 1

return opt[x][y] + a[i]

选 j 类似

0

jacklv LV 10 @ 12 年前
这题虽然破百了，但是我认为还是值得一写（后悔当初99人的时候没挤一下）

先倒着动规求出f表示某个人取时可以取到的最大值。这个时候还是要做个函数比较方便吧，这个状态是和它倒退k-1步有关的，因为别人还要取。用g表示在面对i到j的数列时取i则g=1 else g=2 ，g的处理对倒退k-1步和最后求每个人取到的数也是有关的

t1=back(i+1,j); t2=back(i,j-1);

if t1+a[i]>t2+a[j] then

begin

f=t1+a[i];

g:=1;

end else ...

最后对于每个人若是他的回合，他面对的数列是i~j

则用g去判断他是取i优还是取j优

总的算法复杂度是（n*n*k）吧

还是过的去的

0

yzl609271536 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 494ms

├ 测试数据 02：答案正确... 447ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1538ms

第100个

这题应该归到DP

0

陈亮宇 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 711ms

├ 测试数据 02：答案正确... 618ms

├ 测试数据 03：答案正确... 306ms

├ 测试数据 04：答案正确... 508ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2143ms

啊蛤蛤 虽然 时间比较慢

此题 第99个AC 的人~

~ AC ~ 100 ~ 题庆

100/321(31%) 　

通过 　　99人

调试了好久 原来是动态规划 。。。 枚举边界问题啊！

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 338ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1116ms

e开头的那个评测机

好了些

0

TLD LV 10 @ 12 年前
其实用个结构体做个返回值就可以了

0

怪盗~基德 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

这时间还真不爽，动规题就该秒杀的。。。。。。

0

mike_nzk LV 10 @ 12 年前
这种沙茶题还3次AC...太弱了...

0

LV 0 @ 12 年前
大牛说的没错，因为每次都保留了决策，做的时候往前推k-1步就知道取i优还是取j优了。

贴下主过程～

但我这样做暴慢～～～，再推k步(back函数）的时候能否优化呢？

for l:=2 to n do

begin

for i:=1 to n-l+1 do

begin

j:=i+l-1;

k1:=back(i+1,j);

k2:=back(i,j-1);

if k1+p[i]>k2+p[j] then begin

f:=k1+p[i];

g:=1;

end

else begin

f:=k2+p[j];

g:=2;

end;

end;

end;

0

k103701 LV 10 @ 13 年前
编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

一个地方改了3遍,从p

0

notblack LV 10 @ 13 年前
样例有什么意义..............

0

junlonely LV 7 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜whqlsc牛牛。！~

0

dengailing LV 3 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多亏了楼上的牛啊。。。。。。。。。。。。。。。

清哥加油！！！！！！！！~~~~~~~~~~~~~~~~

0

FancyMouse LV 3 @ 14 年前
记录状态转移的时候只能逆推（因为某个状态顺推可能有两解）

补充一句……case4我有理由怀疑输入数据少了一个数。即in文件里只有999个数。

大多数人都把变量设为全局变量，因此默认为0——这也是标程默认的，因此以前没人发现这个问题- -

所以，如果是把数据输入局部变量的话，请不要忘记清0。。。

0

zyz915 LV 8 @ 14 年前
唔,总算,想了好久的DP啊...

0

gamejifan LV 7 @ 15 年前
本人主要功绩就是把这题通过率拉下来一个百分点。

我靠。。我只不过DP的时候用了它80MB的内存就说我溢出了，害得我只能用滚动数组

0

thebeet LV 3 @ 15 年前
此题其实和１２０２差不多．．．

做决策的时候　就是多往前面推K步

1 2 下一页 › 末页 »
Advanced Selection
查看题目
递交
讨论
题解
信息
ID1207递交 Accepted难度4分类点击显示标签(无)递交数197我的递交数1已通过79通过率40%被复制3上传者 lolanv
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

0

ljt12138 LV 10 @ 5 年前
还是挺有意思的一道题。
用dp做敌对搜索的思路很巧妙！

0

prince_hao LV 10 @ 11 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

第一次忘记限制下标了结果是WA...

0

voyagec2 LV 10 @ 12 年前
原来如此..

0

ShingRay LV 10 @ 12 年前
opt[i][j] 表示对于 i~j，当前面临选择的同学最大取得的和

有两种选法，选 i 和选 j

pre[i][j]: 面临 i~j 时最优选择方案， 0:选i；1:选j

若选 i

x, y, kk = i+1, j, k-1

while kk > 0:

__|_if pre[x][y] == 0: x += 1

__|_else: y -= 1

___|_kk -= 1

return opt[x][y] + a[i]

选 j 类似

0

jacklv LV 10 @ 12 年前
这题虽然破百了，但是我认为还是值得一写（后悔当初99人的时候没挤一下）

先倒着动规求出f表示某个人取时可以取到的最大值。这个时候还是要做个函数比较方便吧，这个状态是和它倒退k-1步有关的，因为别人还要取。用g表示在面对i到j的数列时取i则g=1 else g=2 ，g的处理对倒退k-1步和最后求每个人取到的数也是有关的

t1=back(i+1,j); t2=back(i,j-1);

if t1+a[i]>t2+a[j] then

begin

f=t1+a[i];

g:=1;

end else ...

最后对于每个人若是他的回合，他面对的数列是i~j

则用g去判断他是取i优还是取j优

总的算法复杂度是（n*n*k）吧

还是过的去的

0

yzl609271536 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 494ms

├ 测试数据 02：答案正确... 447ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1538ms

第100个

这题应该归到DP

0

陈亮宇 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 711ms

├ 测试数据 02：答案正确... 618ms

├ 测试数据 03：答案正确... 306ms

├ 测试数据 04：答案正确... 508ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2143ms

啊蛤蛤 虽然 时间比较慢

此题 第99个AC 的人~

~ AC ~ 100 ~ 题庆

100/321(31%) 　

通过 　　99人

调试了好久 原来是动态规划 。。。 枚举边界问题啊！

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 338ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1116ms

e开头的那个评测机

好了些

0

TLD LV 10 @ 12 年前
其实用个结构体做个返回值就可以了

0

怪盗~基德 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

这时间还真不爽，动规题就该秒杀的。。。。。。

0

mike_nzk LV 10 @ 12 年前
这种沙茶题还3次AC...太弱了...

0

LV 0 @ 12 年前
大牛说的没错，因为每次都保留了决策，做的时候往前推k-1步就知道取i优还是取j优了。

贴下主过程～

但我这样做暴慢～～～，再推k步(back函数）的时候能否优化呢？

for l:=2 to n do

begin

for i:=1 to n-l+1 do

begin

j:=i+l-1;

k1:=back(i+1,j);

k2:=back(i,j-1);

if k1+p[i]>k2+p[j] then begin

f:=k1+p[i];

g:=1;

end

else begin

f:=k2+p[j];

g:=2;

end;

end;

end;

0

k103701 LV 10 @ 13 年前
编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

一个地方改了3遍,从p

0

notblack LV 10 @ 13 年前
样例有什么意义..............

0

junlonely LV 7 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜whqlsc牛牛。！~

0

dengailing LV 3 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多亏了楼上的牛啊。。。。。。。。。。。。。。。

清哥加油！！！！！！！！~~~~~~~~~~~~~~~~

0

FancyMouse LV 3 @ 14 年前
记录状态转移的时候只能逆推（因为某个状态顺推可能有两解）

补充一句……case4我有理由怀疑输入数据少了一个数。即in文件里只有999个数。

大多数人都把变量设为全局变量，因此默认为0——这也是标程默认的，因此以前没人发现这个问题- -

所以，如果是把数据输入局部变量的话，请不要忘记清0。。。

0

zyz915 LV 8 @ 14 年前
唔,总算,想了好久的DP啊...

1 2 下一页 › 末页 »
Advanced Selection
查看题目
递交
讨论
题解
信息
ID1207递交 Accepted难度4分类点击显示标签(无)递交数197我的递交数1已通过79通过率40%被复制3上传者 lolanv
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

0

real_hdsy_gyz LV 0 @ 刚刚

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / Advanced Selection /
题解
25 条题解
0
real_hdsy_gyz LV 0
发表您的题解
2

PowderHan LV 10 @ 4 年前
/*
一道不是很难的动态规划 rp竟然这么高
但是的确很考验思维能力的博弈题
嗯和那个啥P1202有点像(一类) 先去做通P1202
嗯状态是一样的
f[i,j]表示[i,j]中的最大值，但注意只存一个人的
首先需要注意到一个性质：
当确定了哪段[i,j]之后，最后哪个人拿数（i或者j）是确定的，
因此枚举拿i还是拿j，那么哪个更加优呢？
我们可以给每个f[I,j]存一个g[I,j]表示决策，然后往前推k步就行了
即设f[i,j]表示i到j轮到的人能取的最大值
g[i,j]=1表示取i，g[i,j]=2表示取j那么
f[i,j]=max(a[i]+get(i+1，j),a[j]+get(i,j-1))（倒着取）
get函数是用来求上次此人取得的最大值
即我们可以看到k个人实际上是轮流选择这个最优解的
那么比如第x个人 我们枚举他是取左边还是右边
那我们肯定是要考虑到我们要有
a[i]+(选了a[i]后可以达到的最大值)和a[j]+(选了a[j]后的最大值)要取最大值
那么我们怎么得到选了a[i]或a[j]后可以达到的最大值呢？
我们已经用g[i][j]记录了做[i,j]这个区间决策的时候是选取左边还是右边
所以我们就向前推k-1步 即k-1次取数就是上一轮这个人的时候选取得到的最大值
和1202一样我们的每一个决策都是从一个比它短的区间递推而来
所以我们肯定在[i-1,j]或者[i,j-1]中的所有需要的f[][]和g[][]都已经球出来了
所以我们在[i-1][j]和[i,j-1]中推一遍
仔细考虑这个递推的过程
我们看一直将这个区间缩短 如果g[x][y]==1说明这一个区间最优取的是x
则转换为了[x-1,y]中的问题 x--
同理g[x][y]==2 则y--
那么就有两种情况了，这个人是第一次选数字 那么肯定推不到他上次选数的情况
就会出现x>y了 如果没有出现这种情况 那么我们在循环k-1次后
得到的新的f[x][y]一定就是他上次选数之后的最优解了
所以我们就可以根据情况返回0或者f[x][y]
这个函数很重要考虑到了一种DP递推的思路
至于输出答案
我们就按照f[][]和g[][]走一遍
当走完k个人的时候 肯定就将每个人的最优解得出来了
好题 锻炼思维了
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1002;
int a[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int n,k;

void init()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],g[i][i]=1,f[i][i]=a[i];
}

int get(int x,int y)//求上次此人取得的最大和
{
for(int i=1;i<=k-1;i++)
if(x>y)
break;
else if(g[x][y]==1)
x++;
else
y--;
if(x<=y)

return f[x][y];
else
return 0;
}

void getans()
{
int x=1; int y=n;
for(int i=1;i<=k;i++)
{
cout<<f[x][y]<<endl;
if(g[x][y]==1)
x++;
else
y--;
}
}

int main()
{
init();
for(int l=1;l<=n-1;l++)//长度
for(int i=1;i<=n-l;i++)//起点
{
int j=i+l;//终点
int x=get(i+1,j);//求出上次
int y=get(i,j-1);//的最大值
if(x+a[i]>y+a[j])
{
f[i][j]=x+a[i];
g[i][j]=1;
}
else
{
f[i][j]=y+a[j];
g[i][j]=2;
}
}
getans();
return 0;
}

Copy
0

real_hdsy_gyz LV 0 @ 26 秒前

艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / Advanced Selection /
题解
24 条题解
0
real_hdsy_gyz LV 0
艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
​

​
​
​
​

2

PowderHan LV 10 @ 4 年前
/*
一道不是很难的动态规划 rp竟然这么高
但是的确很考验思维能力的博弈题
嗯和那个啥P1202有点像(一类) 先去做通P1202
嗯状态是一样的
f[i,j]表示[i,j]中的最大值，但注意只存一个人的
首先需要注意到一个性质：
当确定了哪段[i,j]之后，最后哪个人拿数（i或者j）是确定的，
因此枚举拿i还是拿j，那么哪个更加优呢？
我们可以给每个f[I,j]存一个g[I,j]表示决策，然后往前推k步就行了
即设f[i,j]表示i到j轮到的人能取的最大值
g[i,j]=1表示取i，g[i,j]=2表示取j那么
f[i,j]=max(a[i]+get(i+1，j),a[j]+get(i,j-1))（倒着取）
get函数是用来求上次此人取得的最大值
即我们可以看到k个人实际上是轮流选择这个最优解的
那么比如第x个人 我们枚举他是取左边还是右边
那我们肯定是要考虑到我们要有
a[i]+(选了a[i]后可以达到的最大值)和a[j]+(选了a[j]后的最大值)要取最大值
那么我们怎么得到选了a[i]或a[j]后可以达到的最大值呢？
我们已经用g[i][j]记录了做[i,j]这个区间决策的时候是选取左边还是右边
所以我们就向前推k-1步 即k-1次取数就是上一轮这个人的时候选取得到的最大值
和1202一样我们的每一个决策都是从一个比它短的区间递推而来
所以我们肯定在[i-1,j]或者[i,j-1]中的所有需要的f[][]和g[][]都已经球出来了
所以我们在[i-1][j]和[i,j-1]中推一遍
仔细考虑这个递推的过程
我们看一直将这个区间缩短 如果g[x][y]==1说明这一个区间最优取的是x
则转换为了[x-1,y]中的问题 x--
同理g[x][y]==2 则y--
那么就有两种情况了，这个人是第一次选数字 那么肯定推不到他上次选数的情况
就会出现x>y了 如果没有出现这种情况 那么我们在循环k-1次后
得到的新的f[x][y]一定就是他上次选数之后的最优解了
所以我们就可以根据情况返回0或者f[x][y]
这个函数很重要考虑到了一种DP递推的思路
至于输出答案
我们就按照f[][]和g[][]走一遍
当走完k个人的时候 肯定就将每个人的最优解得出来了
好题 锻炼思维了
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1002;
int a[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int n,k;

void init()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],g[i][i]=1,f[i][i]=a[i];
}

int get(int x,int y)//求上次此人取得的最大和
{
for(int i=1;i<=k-1;i++)
if(x>y)
break;
else if(g[x][y]==1)
x++;
else
y--;
if(x<=y)

return f[x][y];
else
return 0;
}

void getans()
{
int x=1; int y=n;
for(int i=1;i<=k;i++)
{
cout<<f[x][y]<<endl;
if(g[x][y]==1)
x++;
else
y--;
}
}

int main()
{
init();
for(int l=1;l<=n-1;l++)//长度
for(int i=1;i<=n-l;i++)//起点
{
int j=i+l;//终点
int x=get(i+1,j);//求出上次
int y=get(i,j-1);//的最大值
if(x+a[i]>y+a[j])
{
f[i][j]=x+a[i];
g[i][j]=1;
}
else
{
f[i][j]=y+a[j];
g[i][j]=2;
}
}
getans();
return 0;
}

Copy
0

ljt12138 LV 10 @ 5 年前
还是挺有意思的一道题。
用dp做敌对搜索的思路很巧妙！

0

prince_hao LV 10 @ 11 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

第一次忘记限制下标了结果是WA...

0

voyagec2 LV 10 @ 12 年前
原来如此..

0

ShingRay LV 10 @ 12 年前
opt[i][j] 表示对于 i~j，当前面临选择的同学最大取得的和

有两种选法，选 i 和选 j

pre[i][j]: 面临 i~j 时最优选择方案， 0:选i；1:选j

若选 i

x, y, kk = i+1, j, k-1

while kk > 0:

__|_if pre[x][y] == 0: x += 1

__|_else: y -= 1

___|_kk -= 1

return opt[x][y] + a[i]

选 j 类似

0

jacklv LV 10 @ 12 年前
这题虽然破百了，但是我认为还是值得一写（后悔当初99人的时候没挤一下）

先倒着动规求出f表示某个人取时可以取到的最大值。这个时候还是要做个函数比较方便吧，这个状态是和它倒退k-1步有关的，因为别人还要取。用g表示在面对i到j的数列时取i则g=1 else g=2 ，g的处理对倒退k-1步和最后求每个人取到的数也是有关的

t1=back(i+1,j); t2=back(i,j-1);

if t1+a[i]>t2+a[j] then

begin

f=t1+a[i];

g:=1;

end else ...

最后对于每个人若是他的回合，他面对的数列是i~j

则用g去判断他是取i优还是取j优

总的算法复杂度是（n*n*k）吧

还是过的去的

0

yzl609271536 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 494ms

├ 测试数据 02：答案正确... 447ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1538ms

第100个

这题应该归到DP

0

陈亮宇 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 711ms

├ 测试数据 02：答案正确... 618ms

├ 测试数据 03：答案正确... 306ms

├ 测试数据 04：答案正确... 508ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2143ms

啊蛤蛤 虽然 时间比较慢

此题 第99个AC 的人~

~ AC ~ 100 ~ 题庆

100/321(31%) 　

通过 　　99人

调试了好久 原来是动态规划 。。。 枚举边界问题啊！

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 338ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1116ms

e开头的那个评测机

好了些

0

TLD LV 10 @ 12 年前
其实用个结构体做个返回值就可以了

0

怪盗~基德 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

这时间还真不爽，动规题就该秒杀的。。。。。。

0

mike_nzk LV 10 @ 12 年前
这种沙茶题还3次AC...太弱了...

0

LV 0 @ 12 年前
大牛说的没错，因为每次都保留了决策，做的时候往前推k-1步就知道取i优还是取j优了。

贴下主过程～

但我这样做暴慢～～～，再推k步(back函数）的时候能否优化呢？

for l:=2 to n do

begin

for i:=1 to n-l+1 do

begin

j:=i+l-1;

k1:=back(i+1,j);

k2:=back(i,j-1);

if k1+p[i]>k2+p[j] then begin

f:=k1+p[i];

g:=1;

end

else begin

f:=k2+p[j];

g:=2;

end;

end;

end;

0

k103701 LV 10 @ 13 年前
编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

一个地方改了3遍,从p

0

notblack LV 10 @ 13 年前
样例有什么意义..............

0

junlonely LV 7 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜whqlsc牛牛。！~

0

dengailing LV 3 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多亏了楼上的牛啊。。。。。。。。。。。。。。。

清哥加油！！！！！！！！~~~~~~~~~~~~~~~~

0

FancyMouse LV 3 @ 14 年前
记录状态转移的时候只能逆推（因为某个状态顺推可能有两解）

补充一句……case4我有理由怀疑输入数据少了一个数。即in文件里只有999个数。

大多数人都把变量设为全局变量，因此默认为0——这也是标程默认的，因此以前没人发现这个问题- -

所以，如果是把数据输入局部变量的话，请不要忘记清0。。。

0

zyz915 LV 8 @ 14 年前
唔,总算,想了好久的DP啊...

0

gamejifan LV 7 @ 15 年前
本人主要功绩就是把这题通过率拉下来一个百分点。

我靠。。我只不过DP的时候用了它80MB的内存就说我溢出了，害得我只能用滚动数组

0

thebeet LV 3 @ 15 年前
此题其实和１２０２差不多．．．

做决策的时候　就是多往前面推K步

1 2 下一页 › 末页 »
Advanced Selection
查看题目
递交
讨论
题解
信息
ID1207递交 Accepted难度4分类点击显示标签(无)递交数197我的递交数1已通过79通过率40%被复制3上传者 lolanv
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

0

ljt12138 LV 10 @ 5 年前
还是挺有意思的一道题。
用dp做敌对搜索的思路很巧妙！

0

prince_hao LV 10 @ 11 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

第一次忘记限制下标了结果是WA...

0

voyagec2 LV 10 @ 12 年前
原来如此..

0

ShingRay LV 10 @ 12 年前
opt[i][j] 表示对于 i~j，当前面临选择的同学最大取得的和

有两种选法，选 i 和选 j

pre[i][j]: 面临 i~j 时最优选择方案， 0:选i；1:选j

若选 i

x, y, kk = i+1, j, k-1

while kk > 0:

__|_if pre[x][y] == 0: x += 1

__|_else: y -= 1

___|_kk -= 1

return opt[x][y] + a[i]

选 j 类似

0

jacklv LV 10 @ 12 年前
这题虽然破百了，但是我认为还是值得一写（后悔当初99人的时候没挤一下）

先倒着动规求出f表示某个人取时可以取到的最大值。这个时候还是要做个函数比较方便吧，这个状态是和它倒退k-1步有关的，因为别人还要取。用g表示在面对i到j的数列时取i则g=1 else g=2 ，g的处理对倒退k-1步和最后求每个人取到的数也是有关的

t1=back(i+1,j); t2=back(i,j-1);

if t1+a[i]>t2+a[j] then

begin

f=t1+a[i];

g:=1;

end else ...

最后对于每个人若是他的回合，他面对的数列是i~j

则用g去判断他是取i优还是取j优

总的算法复杂度是（n*n*k）吧

还是过的去的

0

yzl609271536 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 494ms

├ 测试数据 02：答案正确... 447ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1538ms

第100个

这题应该归到DP

0

陈亮宇 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 711ms

├ 测试数据 02：答案正确... 618ms

├ 测试数据 03：答案正确... 306ms

├ 测试数据 04：答案正确... 508ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2143ms

啊蛤蛤 虽然 时间比较慢

此题 第99个AC 的人~

~ AC ~ 100 ~ 题庆

100/321(31%) 　

通过 　　99人

调试了好久 原来是动态规划 。。。 枚举边界问题啊！

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 338ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1116ms

e开头的那个评测机

好了些

0

TLD LV 10 @ 12 年前
其实用个结构体做个返回值就可以了

0

怪盗~基德 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

这时间还真不爽，动规题就该秒杀的。。。。。。

0

mike_nzk LV 10 @ 12 年前
这种沙茶题还3次AC...太弱了...

0

LV 0 @ 12 年前
大牛说的没错，因为每次都保留了决策，做的时候往前推k-1步就知道取i优还是取j优了。

贴下主过程～

但我这样做暴慢～～～，再推k步(back函数）的时候能否优化呢？

for l:=2 to n do

begin

for i:=1 to n-l+1 do

begin

j:=i+l-1;

k1:=back(i+1,j);

k2:=back(i,j-1);

if k1+p[i]>k2+p[j] then begin

f:=k1+p[i];

g:=1;

end

else begin

f:=k2+p[j];

g:=2;

end;

end;

end;

0

k103701 LV 10 @ 13 年前
编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

一个地方改了3遍,从p

0

notblack LV 10 @ 13 年前
样例有什么意义..............

0

junlonely LV 7 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜whqlsc牛牛。！~

0

dengailing LV 3 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多亏了楼上的牛啊。。。。。。。。。。。。。。。

清哥加油！！！！！！！！~~~~~~~~~~~~~~~~

0

FancyMouse LV 3 @ 14 年前
记录状态转移的时候只能逆推（因为某个状态顺推可能有两解）

补充一句……case4我有理由怀疑输入数据少了一个数。即in文件里只有999个数。

大多数人都把变量设为全局变量，因此默认为0——这也是标程默认的，因此以前没人发现这个问题- -

所以，如果是把数据输入局部变量的话，请不要忘记清0。。。

0

zyz915 LV 8 @ 14 年前
唔,总算,想了好久的DP啊...

0

gamejifan LV 7 @ 15 年前
本人主要功绩就是把这题通过率拉下来一个百分点。

我靠。。我只不过DP的时候用了它80MB的内存就说我溢出了，害得我只能用滚动数组

1 2 下一页 › 末页 »
Advanced Selection
查看题目
递交
讨论
题解
信息
ID1207递交 Accepted难度4分类点击显示标签(无)递交数197我的递交数1已通过79通过率40%被复制3上传者 lolanv
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

0

real_hdsy_gyz LV 0 @ 38 秒前

艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / Advanced Selection /
题解
24 条题解
0
real_hdsy_gyz LV 0
艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
​

​
​
​
​

2

PowderHan LV 10 @ 4 年前
/*
一道不是很难的动态规划 rp竟然这么高
但是的确很考验思维能力的博弈题
嗯和那个啥P1202有点像(一类) 先去做通P1202
嗯状态是一样的
f[i,j]表示[i,j]中的最大值，但注意只存一个人的
首先需要注意到一个性质：
当确定了哪段[i,j]之后，最后哪个人拿数（i或者j）是确定的，
因此枚举拿i还是拿j，那么哪个更加优呢？
我们可以给每个f[I,j]存一个g[I,j]表示决策，然后往前推k步就行了
即设f[i,j]表示i到j轮到的人能取的最大值
g[i,j]=1表示取i，g[i,j]=2表示取j那么
f[i,j]=max(a[i]+get(i+1，j),a[j]+get(i,j-1))（倒着取）
get函数是用来求上次此人取得的最大值
即我们可以看到k个人实际上是轮流选择这个最优解的
那么比如第x个人 我们枚举他是取左边还是右边
那我们肯定是要考虑到我们要有
a[i]+(选了a[i]后可以达到的最大值)和a[j]+(选了a[j]后的最大值)要取最大值
那么我们怎么得到选了a[i]或a[j]后可以达到的最大值呢？
我们已经用g[i][j]记录了做[i,j]这个区间决策的时候是选取左边还是右边
所以我们就向前推k-1步 即k-1次取数就是上一轮这个人的时候选取得到的最大值
和1202一样我们的每一个决策都是从一个比它短的区间递推而来
所以我们肯定在[i-1,j]或者[i,j-1]中的所有需要的f[][]和g[][]都已经球出来了
所以我们在[i-1][j]和[i,j-1]中推一遍
仔细考虑这个递推的过程
我们看一直将这个区间缩短 如果g[x][y]==1说明这一个区间最优取的是x
则转换为了[x-1,y]中的问题 x--
同理g[x][y]==2 则y--
那么就有两种情况了，这个人是第一次选数字 那么肯定推不到他上次选数的情况
就会出现x>y了 如果没有出现这种情况 那么我们在循环k-1次后
得到的新的f[x][y]一定就是他上次选数之后的最优解了
所以我们就可以根据情况返回0或者f[x][y]
这个函数很重要考虑到了一种DP递推的思路
至于输出答案
我们就按照f[][]和g[][]走一遍
当走完k个人的时候 肯定就将每个人的最优解得出来了
好题 锻炼思维了
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1002;
int a[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int n,k;

void init()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],g[i][i]=1,f[i][i]=a[i];
}

int get(int x,int y)//求上次此人取得的最大和
{
for(int i=1;i<=k-1;i++)
if(x>y)
break;
else if(g[x][y]==1)
x++;
else
y--;
if(x<=y)

return f[x][y];
else
return 0;
}

void getans()
{
int x=1; int y=n;
for(int i=1;i<=k;i++)
{
cout<<f[x][y]<<endl;
if(g[x][y]==1)
x++;
else
y--;
}
}

int main()
{
init();
for(int l=1;l<=n-1;l++)//长度
for(int i=1;i<=n-l;i++)//起点
{
int j=i+l;//终点
int x=get(i+1,j);//求出上次
int y=get(i,j-1);//的最大值
if(x+a[i]>y+a[j])
{
f[i][j]=x+a[i];
g[i][j]=1;
}
else
{
f[i][j]=y+a[j];
g[i][j]=2;
}
}
getans();
return 0;
}

Copy
0

ljt12138 LV 10 @ 5 年前
还是挺有意思的一道题。
用dp做敌对搜索的思路很巧妙！

0

prince_hao LV 10 @ 11 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

第一次忘记限制下标了结果是WA...

0

voyagec2 LV 10 @ 12 年前
原来如此..

0

ShingRay LV 10 @ 12 年前
opt[i][j] 表示对于 i~j，当前面临选择的同学最大取得的和

有两种选法，选 i 和选 j

pre[i][j]: 面临 i~j 时最优选择方案， 0:选i；1:选j

若选 i

x, y, kk = i+1, j, k-1

while kk > 0:

__|_if pre[x][y] == 0: x += 1

__|_else: y -= 1

___|_kk -= 1

return opt[x][y] + a[i]

选 j 类似

0

jacklv LV 10 @ 12 年前
这题虽然破百了，但是我认为还是值得一写（后悔当初99人的时候没挤一下）

先倒着动规求出f表示某个人取时可以取到的最大值。这个时候还是要做个函数比较方便吧，这个状态是和它倒退k-1步有关的，因为别人还要取。用g表示在面对i到j的数列时取i则g=1 else g=2 ，g的处理对倒退k-1步和最后求每个人取到的数也是有关的

t1=back(i+1,j); t2=back(i,j-1);

if t1+a[i]>t2+a[j] then

begin

f=t1+a[i];

g:=1;

end else ...

最后对于每个人若是他的回合，他面对的数列是i~j

则用g去判断他是取i优还是取j优

总的算法复杂度是（n*n*k）吧

还是过的去的

0

yzl609271536 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 494ms

├ 测试数据 02：答案正确... 447ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1538ms

第100个

这题应该归到DP

0

陈亮宇 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 711ms

├ 测试数据 02：答案正确... 618ms

├ 测试数据 03：答案正确... 306ms

├ 测试数据 04：答案正确... 508ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2143ms

啊蛤蛤 虽然 时间比较慢

此题 第99个AC 的人~

~ AC ~ 100 ~ 题庆

100/321(31%) 　

通过 　　99人

调试了好久 原来是动态规划 。。。 枚举边界问题啊！

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 338ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1116ms

e开头的那个评测机

好了些

0

TLD LV 10 @ 12 年前
其实用个结构体做个返回值就可以了

0

怪盗~基德 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

这时间还真不爽，动规题就该秒杀的。。。。。。

0

mike_nzk LV 10 @ 12 年前
这种沙茶题还3次AC...太弱了...

0

LV 0 @ 12 年前
大牛说的没错，因为每次都保留了决策，做的时候往前推k-1步就知道取i优还是取j优了。

贴下主过程～

但我这样做暴慢～～～，再推k步(back函数）的时候能否优化呢？

for l:=2 to n do

begin

for i:=1 to n-l+1 do

begin

j:=i+l-1;

k1:=back(i+1,j);

k2:=back(i,j-1);

if k1+p[i]>k2+p[j] then begin

f:=k1+p[i];

g:=1;

end

else begin

f:=k2+p[j];

g:=2;

end;

end;

end;

0

k103701 LV 10 @ 13 年前
编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

一个地方改了3遍,从p

0

notblack LV 10 @ 13 年前
样例有什么意义..............

0

junlonely LV 7 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜whqlsc牛牛。！~

0

dengailing LV 3 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多亏了楼上的牛啊。。。。。。。。。。。。。。。

清哥加油！！！！！！！！~~~~~~~~~~~~~~~~

0

FancyMouse LV 3 @ 14 年前
记录状态转移的时候只能逆推（因为某个状态顺推可能有两解）

补充一句……case4我有理由怀疑输入数据少了一个数。即in文件里只有999个数。

大多数人都把变量设为全局变量，因此默认为0——这也是标程默认的，因此以前没人发现这个问题- -

所以，如果是把数据输入局部变量的话，请不要忘记清0。。。

0

zyz915 LV 8 @ 14 年前
唔,总算,想了好久的DP啊...

0

gamejifan LV 7 @ 15 年前
本人主要功绩就是把这题通过率拉下来一个百分点。

我靠。。我只不过DP的时候用了它80MB的内存就说我溢出了，害得我只能用滚动数组

0

thebeet LV 3 @ 15 年前
此题其实和１２０２差不多．．．

做决策的时候　就是多往前面推K步

1 2 下一页 › 末页 »
Advanced Selection
查看题目
递交
讨论
题解
信息
ID1207递交 Accepted难度4分类点击显示标签(无)递交数197我的递交数1已通过79通过率40%被复制3上传者 lolanv
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

0

ljt12138 LV 10 @ 5 年前
还是挺有意思的一道题。
用dp做敌对搜索的思路很巧妙！

0

prince_hao LV 10 @ 11 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

第一次忘记限制下标了结果是WA...

0

voyagec2 LV 10 @ 12 年前
原来如此..

0

ShingRay LV 10 @ 12 年前
opt[i][j] 表示对于 i~j，当前面临选择的同学最大取得的和

有两种选法，选 i 和选 j

pre[i][j]: 面临 i~j 时最优选择方案， 0:选i；1:选j

若选 i

x, y, kk = i+1, j, k-1

while kk > 0:

__|_if pre[x][y] == 0: x += 1

__|_else: y -= 1

___|_kk -= 1

return opt[x][y] + a[i]

选 j 类似

0

jacklv LV 10 @ 12 年前
这题虽然破百了，但是我认为还是值得一写（后悔当初99人的时候没挤一下）

先倒着动规求出f表示某个人取时可以取到的最大值。这个时候还是要做个函数比较方便吧，这个状态是和它倒退k-1步有关的，因为别人还要取。用g表示在面对i到j的数列时取i则g=1 else g=2 ，g的处理对倒退k-1步和最后求每个人取到的数也是有关的

t1=back(i+1,j); t2=back(i,j-1);

if t1+a[i]>t2+a[j] then

begin

f=t1+a[i];

g:=1;

end else ...

最后对于每个人若是他的回合，他面对的数列是i~j

则用g去判断他是取i优还是取j优

总的算法复杂度是（n*n*k）吧

还是过的去的

0

yzl609271536 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 494ms

├ 测试数据 02：答案正确... 447ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1538ms

第100个

这题应该归到DP

0

陈亮宇 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 711ms

├ 测试数据 02：答案正确... 618ms

├ 测试数据 03：答案正确... 306ms

├ 测试数据 04：答案正确... 508ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2143ms

啊蛤蛤 虽然 时间比较慢

此题 第99个AC 的人~

~ AC ~ 100 ~ 题庆

100/321(31%) 　

通过 　　99人

调试了好久 原来是动态规划 。。。 枚举边界问题啊！

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 338ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1116ms

e开头的那个评测机

好了些

0

TLD LV 10 @ 12 年前
其实用个结构体做个返回值就可以了

0

怪盗~基德 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

这时间还真不爽，动规题就该秒杀的。。。。。。

0

mike_nzk LV 10 @ 12 年前
这种沙茶题还3次AC...太弱了...

0

LV 0 @ 12 年前
大牛说的没错，因为每次都保留了决策，做的时候往前推k-1步就知道取i优还是取j优了。

贴下主过程～

但我这样做暴慢～～～，再推k步(back函数）的时候能否优化呢？

for l:=2 to n do

begin

for i:=1 to n-l+1 do

begin

j:=i+l-1;

k1:=back(i+1,j);

k2:=back(i,j-1);

if k1+p[i]>k2+p[j] then begin

f:=k1+p[i];

g:=1;

end

else begin

f:=k2+p[j];

g:=2;

end;

end;

end;

0

k103701 LV 10 @ 13 年前
编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

一个地方改了3遍,从p

0

notblack LV 10 @ 13 年前
样例有什么意义..............

0

junlonely LV 7 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜whqlsc牛牛。！~

0

dengailing LV 3 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多亏了楼上的牛啊。。。。。。。。。。。。。。。

清哥加油！！！！！！！！~~~~~~~~~~~~~~~~

0

FancyMouse LV 3 @ 14 年前
记录状态转移的时候只能逆推（因为某个状态顺推可能有两解）

补充一句……case4我有理由怀疑输入数据少了一个数。即in文件里只有999个数。

大多数人都把变量设为全局变量，因此默认为0——这也是标程默认的，因此以前没人发现这个问题- -

所以，如果是把数据输入局部变量的话，请不要忘记清0。。。

1 2 下一页 › 末页 »
Advanced Selection
查看题目
递交
讨论
题解
信息
ID1207递交 Accepted难度4分类点击显示标签(无)递交数197我的递交数1已通过79通过率40%被复制3上传者 lolanv
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / Advanced Selection /
题解
26 条题解
0
real_hdsy_gyz LV 0
发表您的题解
2

PowderHan LV 10 @ 4 年前
/*
一道不是很难的动态规划 rp竟然这么高
但是的确很考验思维能力的博弈题
嗯和那个啥P1202有点像(一类) 先去做通P1202
嗯状态是一样的
f[i,j]表示[i,j]中的最大值，但注意只存一个人的
首先需要注意到一个性质：
当确定了哪段[i,j]之后，最后哪个人拿数（i或者j）是确定的，
因此枚举拿i还是拿j，那么哪个更加优呢？
我们可以给每个f[I,j]存一个g[I,j]表示决策，然后往前推k步就行了
即设f[i,j]表示i到j轮到的人能取的最大值
g[i,j]=1表示取i，g[i,j]=2表示取j那么
f[i,j]=max(a[i]+get(i+1，j),a[j]+get(i,j-1))（倒着取）
get函数是用来求上次此人取得的最大值
即我们可以看到k个人实际上是轮流选择这个最优解的
那么比如第x个人 我们枚举他是取左边还是右边
那我们肯定是要考虑到我们要有
a[i]+(选了a[i]后可以达到的最大值)和a[j]+(选了a[j]后的最大值)要取最大值
那么我们怎么得到选了a[i]或a[j]后可以达到的最大值呢？
我们已经用g[i][j]记录了做[i,j]这个区间决策的时候是选取左边还是右边
所以我们就向前推k-1步 即k-1次取数就是上一轮这个人的时候选取得到的最大值
和1202一样我们的每一个决策都是从一个比它短的区间递推而来
所以我们肯定在[i-1,j]或者[i,j-1]中的所有需要的f[][]和g[][]都已经球出来了
所以我们在[i-1][j]和[i,j-1]中推一遍
仔细考虑这个递推的过程
我们看一直将这个区间缩短 如果g[x][y]==1说明这一个区间最优取的是x
则转换为了[x-1,y]中的问题 x--
同理g[x][y]==2 则y--
那么就有两种情况了，这个人是第一次选数字 那么肯定推不到他上次选数的情况
就会出现x>y了 如果没有出现这种情况 那么我们在循环k-1次后
得到的新的f[x][y]一定就是他上次选数之后的最优解了
所以我们就可以根据情况返回0或者f[x][y]
这个函数很重要考虑到了一种DP递推的思路
至于输出答案
我们就按照f[][]和g[][]走一遍
当走完k个人的时候 肯定就将每个人的最优解得出来了
好题 锻炼思维了
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1002;
int a[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int n,k;

void init()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],g[i][i]=1,f[i][i]=a[i];
}

int get(int x,int y)//求上次此人取得的最大和
{
for(int i=1;i<=k-1;i++)
if(x>y)
break;
else if(g[x][y]==1)
x++;
else
y--;
if(x<=y)

return f[x][y];
else
return 0;
}

void getans()
{
int x=1; int y=n;
for(int i=1;i<=k;i++)
{
cout<<f[x][y]<<endl;
if(g[x][y]==1)
x++;
else
y--;
}
}

int main()
{
init();
for(int l=1;l<=n-1;l++)//长度
for(int i=1;i<=n-l;i++)//起点
{
int j=i+l;//终点
int x=get(i+1,j);//求出上次
int y=get(i,j-1);//的最大值
if(x+a[i]>y+a[j])
{
f[i][j]=x+a[i];
g[i][j]=1;
}
else
{
f[i][j]=y+a[j];
g[i][j]=2;
}
}
getans();
return 0;
}

Copy
0

real_hdsy_gyz LV 0 @ 刚刚

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / Advanced Selection /
题解
25 条题解
0
real_hdsy_gyz LV 0
发表您的题解
2

PowderHan LV 10 @ 4 年前
/*
一道不是很难的动态规划 rp竟然这么高
但是的确很考验思维能力的博弈题
嗯和那个啥P1202有点像(一类) 先去做通P1202
嗯状态是一样的
f[i,j]表示[i,j]中的最大值，但注意只存一个人的
首先需要注意到一个性质：
当确定了哪段[i,j]之后，最后哪个人拿数（i或者j）是确定的，
因此枚举拿i还是拿j，那么哪个更加优呢？
我们可以给每个f[I,j]存一个g[I,j]表示决策，然后往前推k步就行了
即设f[i,j]表示i到j轮到的人能取的最大值
g[i,j]=1表示取i，g[i,j]=2表示取j那么
f[i,j]=max(a[i]+get(i+1，j),a[j]+get(i,j-1))（倒着取）
get函数是用来求上次此人取得的最大值
即我们可以看到k个人实际上是轮流选择这个最优解的
那么比如第x个人 我们枚举他是取左边还是右边
那我们肯定是要考虑到我们要有
a[i]+(选了a[i]后可以达到的最大值)和a[j]+(选了a[j]后的最大值)要取最大值
那么我们怎么得到选了a[i]或a[j]后可以达到的最大值呢？
我们已经用g[i][j]记录了做[i,j]这个区间决策的时候是选取左边还是右边
所以我们就向前推k-1步 即k-1次取数就是上一轮这个人的时候选取得到的最大值
和1202一样我们的每一个决策都是从一个比它短的区间递推而来
所以我们肯定在[i-1,j]或者[i,j-1]中的所有需要的f[][]和g[][]都已经球出来了
所以我们在[i-1][j]和[i,j-1]中推一遍
仔细考虑这个递推的过程
我们看一直将这个区间缩短 如果g[x][y]==1说明这一个区间最优取的是x
则转换为了[x-1,y]中的问题 x--
同理g[x][y]==2 则y--
那么就有两种情况了，这个人是第一次选数字 那么肯定推不到他上次选数的情况
就会出现x>y了 如果没有出现这种情况 那么我们在循环k-1次后
得到的新的f[x][y]一定就是他上次选数之后的最优解了
所以我们就可以根据情况返回0或者f[x][y]
这个函数很重要考虑到了一种DP递推的思路
至于输出答案
我们就按照f[][]和g[][]走一遍
当走完k个人的时候 肯定就将每个人的最优解得出来了
好题 锻炼思维了
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1002;
int a[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int n,k;

void init()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],g[i][i]=1,f[i][i]=a[i];
}

int get(int x,int y)//求上次此人取得的最大和
{
for(int i=1;i<=k-1;i++)
if(x>y)
break;
else if(g[x][y]==1)
x++;
else
y--;
if(x<=y)

return f[x][y];
else
return 0;
}

void getans()
{
int x=1; int y=n;
for(int i=1;i<=k;i++)
{
cout<<f[x][y]<<endl;
if(g[x][y]==1)
x++;
else
y--;
}
}

int main()
{
init();
for(int l=1;l<=n-1;l++)//长度
for(int i=1;i<=n-l;i++)//起点
{
int j=i+l;//终点
int x=get(i+1,j);//求出上次
int y=get(i,j-1);//的最大值
if(x+a[i]>y+a[j])
{
f[i][j]=x+a[i];
g[i][j]=1;
}
else
{
f[i][j]=y+a[j];
g[i][j]=2;
}
}
getans();
return 0;
}

Copy
0

real_hdsy_gyz LV 0 @ 26 秒前

艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / Advanced Selection /
题解
24 条题解
0
real_hdsy_gyz LV 0
艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
​

​
​
​
​

2

PowderHan LV 10 @ 4 年前
/*
一道不是很难的动态规划 rp竟然这么高
但是的确很考验思维能力的博弈题
嗯和那个啥P1202有点像(一类) 先去做通P1202
嗯状态是一样的
f[i,j]表示[i,j]中的最大值，但注意只存一个人的
首先需要注意到一个性质：
当确定了哪段[i,j]之后，最后哪个人拿数（i或者j）是确定的，
因此枚举拿i还是拿j，那么哪个更加优呢？
我们可以给每个f[I,j]存一个g[I,j]表示决策，然后往前推k步就行了
即设f[i,j]表示i到j轮到的人能取的最大值
g[i,j]=1表示取i，g[i,j]=2表示取j那么
f[i,j]=max(a[i]+get(i+1，j),a[j]+get(i,j-1))（倒着取）
get函数是用来求上次此人取得的最大值
即我们可以看到k个人实际上是轮流选择这个最优解的
那么比如第x个人 我们枚举他是取左边还是右边
那我们肯定是要考虑到我们要有
a[i]+(选了a[i]后可以达到的最大值)和a[j]+(选了a[j]后的最大值)要取最大值
那么我们怎么得到选了a[i]或a[j]后可以达到的最大值呢？
我们已经用g[i][j]记录了做[i,j]这个区间决策的时候是选取左边还是右边
所以我们就向前推k-1步 即k-1次取数就是上一轮这个人的时候选取得到的最大值
和1202一样我们的每一个决策都是从一个比它短的区间递推而来
所以我们肯定在[i-1,j]或者[i,j-1]中的所有需要的f[][]和g[][]都已经球出来了
所以我们在[i-1][j]和[i,j-1]中推一遍
仔细考虑这个递推的过程
我们看一直将这个区间缩短 如果g[x][y]==1说明这一个区间最优取的是x
则转换为了[x-1,y]中的问题 x--
同理g[x][y]==2 则y--
那么就有两种情况了，这个人是第一次选数字 那么肯定推不到他上次选数的情况
就会出现x>y了 如果没有出现这种情况 那么我们在循环k-1次后
得到的新的f[x][y]一定就是他上次选数之后的最优解了
所以我们就可以根据情况返回0或者f[x][y]
这个函数很重要考虑到了一种DP递推的思路
至于输出答案
我们就按照f[][]和g[][]走一遍
当走完k个人的时候 肯定就将每个人的最优解得出来了
好题 锻炼思维了
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1002;
int a[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int n,k;

void init()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],g[i][i]=1,f[i][i]=a[i];
}

int get(int x,int y)//求上次此人取得的最大和
{
for(int i=1;i<=k-1;i++)
if(x>y)
break;
else if(g[x][y]==1)
x++;
else
y--;
if(x<=y)

return f[x][y];
else
return 0;
}

void getans()
{
int x=1; int y=n;
for(int i=1;i<=k;i++)
{
cout<<f[x][y]<<endl;
if(g[x][y]==1)
x++;
else
y--;
}
}

int main()
{
init();
for(int l=1;l<=n-1;l++)//长度
for(int i=1;i<=n-l;i++)//起点
{
int j=i+l;//终点
int x=get(i+1,j);//求出上次
int y=get(i,j-1);//的最大值
if(x+a[i]>y+a[j])
{
f[i][j]=x+a[i];
g[i][j]=1;
}
else
{
f[i][j]=y+a[j];
g[i][j]=2;
}
}
getans();
return 0;
}

Copy
0

ljt12138 LV 10 @ 5 年前
还是挺有意思的一道题。
用dp做敌对搜索的思路很巧妙！

0

prince_hao LV 10 @ 11 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

第一次忘记限制下标了结果是WA...

0

voyagec2 LV 10 @ 12 年前
原来如此..

0

ShingRay LV 10 @ 12 年前
opt[i][j] 表示对于 i~j，当前面临选择的同学最大取得的和

有两种选法，选 i 和选 j

pre[i][j]: 面临 i~j 时最优选择方案， 0:选i；1:选j

若选 i

x, y, kk = i+1, j, k-1

while kk > 0:

__|_if pre[x][y] == 0: x += 1

__|_else: y -= 1

___|_kk -= 1

return opt[x][y] + a[i]

选 j 类似

0

jacklv LV 10 @ 12 年前
这题虽然破百了，但是我认为还是值得一写（后悔当初99人的时候没挤一下）

先倒着动规求出f表示某个人取时可以取到的最大值。这个时候还是要做个函数比较方便吧，这个状态是和它倒退k-1步有关的，因为别人还要取。用g表示在面对i到j的数列时取i则g=1 else g=2 ，g的处理对倒退k-1步和最后求每个人取到的数也是有关的

t1=back(i+1,j); t2=back(i,j-1);

if t1+a[i]>t2+a[j] then

begin

f=t1+a[i];

g:=1;

end else ...

最后对于每个人若是他的回合，他面对的数列是i~j

则用g去判断他是取i优还是取j优

总的算法复杂度是（n*n*k）吧

还是过的去的

0

yzl609271536 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 494ms

├ 测试数据 02：答案正确... 447ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1538ms

第100个

这题应该归到DP

0

陈亮宇 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 711ms

├ 测试数据 02：答案正确... 618ms

├ 测试数据 03：答案正确... 306ms

├ 测试数据 04：答案正确... 508ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2143ms

啊蛤蛤 虽然 时间比较慢

此题 第99个AC 的人~

~ AC ~ 100 ~ 题庆

100/321(31%) 　

通过 　　99人

调试了好久 原来是动态规划 。。。 枚举边界问题啊！

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 338ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1116ms

e开头的那个评测机

好了些

0

TLD LV 10 @ 12 年前
其实用个结构体做个返回值就可以了

0

怪盗~基德 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

这时间还真不爽，动规题就该秒杀的。。。。。。

0

mike_nzk LV 10 @ 12 年前
这种沙茶题还3次AC...太弱了...

0

LV 0 @ 12 年前
大牛说的没错，因为每次都保留了决策，做的时候往前推k-1步就知道取i优还是取j优了。

贴下主过程～

但我这样做暴慢～～～，再推k步(back函数）的时候能否优化呢？

for l:=2 to n do

begin

for i:=1 to n-l+1 do

begin

j:=i+l-1;

k1:=back(i+1,j);

k2:=back(i,j-1);

if k1+p[i]>k2+p[j] then begin

f:=k1+p[i];

g:=1;

end

else begin

f:=k2+p[j];

g:=2;

end;

end;

end;

0

k103701 LV 10 @ 13 年前
编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

一个地方改了3遍,从p

0

notblack LV 10 @ 13 年前
样例有什么意义..............

0

junlonely LV 7 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜whqlsc牛牛。！~

0

dengailing LV 3 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多亏了楼上的牛啊。。。。。。。。。。。。。。。

清哥加油！！！！！！！！~~~~~~~~~~~~~~~~

0

FancyMouse LV 3 @ 14 年前
记录状态转移的时候只能逆推（因为某个状态顺推可能有两解）

补充一句……case4我有理由怀疑输入数据少了一个数。即in文件里只有999个数。

大多数人都把变量设为全局变量，因此默认为0——这也是标程默认的，因此以前没人发现这个问题- -

所以，如果是把数据输入局部变量的话，请不要忘记清0。。。

0

zyz915 LV 8 @ 14 年前
唔,总算,想了好久的DP啊...

0

gamejifan LV 7 @ 15 年前
本人主要功绩就是把这题通过率拉下来一个百分点。

我靠。。我只不过DP的时候用了它80MB的内存就说我溢出了，害得我只能用滚动数组

0

thebeet LV 3 @ 15 年前
此题其实和１２０２差不多．．．

做决策的时候　就是多往前面推K步

1 2 下一页 › 末页 »
Advanced Selection
查看题目
递交
讨论
题解
信息
ID1207递交 Accepted难度4分类点击显示标签(无)递交数197我的递交数1已通过79通过率40%被复制3上传者 lolanv
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

0

ljt12138 LV 10 @ 5 年前
还是挺有意思的一道题。
用dp做敌对搜索的思路很巧妙！

0

prince_hao LV 10 @ 11 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

第一次忘记限制下标了结果是WA...

0

voyagec2 LV 10 @ 12 年前
原来如此..

0

ShingRay LV 10 @ 12 年前
opt[i][j] 表示对于 i~j，当前面临选择的同学最大取得的和

有两种选法，选 i 和选 j

pre[i][j]: 面临 i~j 时最优选择方案， 0:选i；1:选j

若选 i

x, y, kk = i+1, j, k-1

while kk > 0:

__|_if pre[x][y] == 0: x += 1

__|_else: y -= 1

___|_kk -= 1

return opt[x][y] + a[i]

选 j 类似

0

jacklv LV 10 @ 12 年前
这题虽然破百了，但是我认为还是值得一写（后悔当初99人的时候没挤一下）

先倒着动规求出f表示某个人取时可以取到的最大值。这个时候还是要做个函数比较方便吧，这个状态是和它倒退k-1步有关的，因为别人还要取。用g表示在面对i到j的数列时取i则g=1 else g=2 ，g的处理对倒退k-1步和最后求每个人取到的数也是有关的

t1=back(i+1,j); t2=back(i,j-1);

if t1+a[i]>t2+a[j] then

begin

f=t1+a[i];

g:=1;

end else ...

最后对于每个人若是他的回合，他面对的数列是i~j

则用g去判断他是取i优还是取j优

总的算法复杂度是（n*n*k）吧

还是过的去的

0

yzl609271536 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 494ms

├ 测试数据 02：答案正确... 447ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1538ms

第100个

这题应该归到DP

0

陈亮宇 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 711ms

├ 测试数据 02：答案正确... 618ms

├ 测试数据 03：答案正确... 306ms

├ 测试数据 04：答案正确... 508ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2143ms

啊蛤蛤 虽然 时间比较慢

此题 第99个AC 的人~

~ AC ~ 100 ~ 题庆

100/321(31%) 　

通过 　　99人

调试了好久 原来是动态规划 。。。 枚举边界问题啊！

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 338ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1116ms

e开头的那个评测机

好了些

0

TLD LV 10 @ 12 年前
其实用个结构体做个返回值就可以了

0

怪盗~基德 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

这时间还真不爽，动规题就该秒杀的。。。。。。

0

mike_nzk LV 10 @ 12 年前
这种沙茶题还3次AC...太弱了...

0

LV 0 @ 12 年前
大牛说的没错，因为每次都保留了决策，做的时候往前推k-1步就知道取i优还是取j优了。

贴下主过程～

但我这样做暴慢～～～，再推k步(back函数）的时候能否优化呢？

for l:=2 to n do

begin

for i:=1 to n-l+1 do

begin

j:=i+l-1;

k1:=back(i+1,j);

k2:=back(i,j-1);

if k1+p[i]>k2+p[j] then begin

f:=k1+p[i];

g:=1;

end

else begin

f:=k2+p[j];

g:=2;

end;

end;

end;

0

k103701 LV 10 @ 13 年前
编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

一个地方改了3遍,从p

0

notblack LV 10 @ 13 年前
样例有什么意义..............

0

junlonely LV 7 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜whqlsc牛牛。！~

0

dengailing LV 3 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多亏了楼上的牛啊。。。。。。。。。。。。。。。

清哥加油！！！！！！！！~~~~~~~~~~~~~~~~

0

FancyMouse LV 3 @ 14 年前
记录状态转移的时候只能逆推（因为某个状态顺推可能有两解）

补充一句……case4我有理由怀疑输入数据少了一个数。即in文件里只有999个数。

大多数人都把变量设为全局变量，因此默认为0——这也是标程默认的，因此以前没人发现这个问题- -

所以，如果是把数据输入局部变量的话，请不要忘记清0。。。

0

zyz915 LV 8 @ 14 年前
唔,总算,想了好久的DP啊...

0

gamejifan LV 7 @ 15 年前
本人主要功绩就是把这题通过率拉下来一个百分点。

我靠。。我只不过DP的时候用了它80MB的内存就说我溢出了，害得我只能用滚动数组

1 2 下一页 › 末页 »
Advanced Selection
查看题目
递交
讨论
题解
信息
ID1207递交 Accepted难度4分类点击显示标签(无)递交数197我的递交数1已通过79通过率40%被复制3上传者 lolanv
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

0

real_hdsy_gyz LV 0 @ 32 秒前

艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / Advanced Selection /
题解
24 条题解
0
real_hdsy_gyz LV 0
艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
​

​
​
​
​

2

PowderHan LV 10 @ 4 年前
/*
一道不是很难的动态规划 rp竟然这么高
但是的确很考验思维能力的博弈题
嗯和那个啥P1202有点像(一类) 先去做通P1202
嗯状态是一样的
f[i,j]表示[i,j]中的最大值，但注意只存一个人的
首先需要注意到一个性质：
当确定了哪段[i,j]之后，最后哪个人拿数（i或者j）是确定的，
因此枚举拿i还是拿j，那么哪个更加优呢？
我们可以给每个f[I,j]存一个g[I,j]表示决策，然后往前推k步就行了
即设f[i,j]表示i到j轮到的人能取的最大值
g[i,j]=1表示取i，g[i,j]=2表示取j那么
f[i,j]=max(a[i]+get(i+1，j),a[j]+get(i,j-1))（倒着取）
get函数是用来求上次此人取得的最大值
即我们可以看到k个人实际上是轮流选择这个最优解的
那么比如第x个人 我们枚举他是取左边还是右边
那我们肯定是要考虑到我们要有
a[i]+(选了a[i]后可以达到的最大值)和a[j]+(选了a[j]后的最大值)要取最大值
那么我们怎么得到选了a[i]或a[j]后可以达到的最大值呢？
我们已经用g[i][j]记录了做[i,j]这个区间决策的时候是选取左边还是右边
所以我们就向前推k-1步 即k-1次取数就是上一轮这个人的时候选取得到的最大值
和1202一样我们的每一个决策都是从一个比它短的区间递推而来
所以我们肯定在[i-1,j]或者[i,j-1]中的所有需要的f[][]和g[][]都已经球出来了
所以我们在[i-1][j]和[i,j-1]中推一遍
仔细考虑这个递推的过程
我们看一直将这个区间缩短 如果g[x][y]==1说明这一个区间最优取的是x
则转换为了[x-1,y]中的问题 x--
同理g[x][y]==2 则y--
那么就有两种情况了，这个人是第一次选数字 那么肯定推不到他上次选数的情况
就会出现x>y了 如果没有出现这种情况 那么我们在循环k-1次后
得到的新的f[x][y]一定就是他上次选数之后的最优解了
所以我们就可以根据情况返回0或者f[x][y]
这个函数很重要考虑到了一种DP递推的思路
至于输出答案
我们就按照f[][]和g[][]走一遍
当走完k个人的时候 肯定就将每个人的最优解得出来了
好题 锻炼思维了
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1002;
int a[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int n,k;

void init()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],g[i][i]=1,f[i][i]=a[i];
}

int get(int x,int y)//求上次此人取得的最大和
{
for(int i=1;i<=k-1;i++)
if(x>y)
break;
else if(g[x][y]==1)
x++;
else
y--;
if(x<=y)

return f[x][y];
else
return 0;
}

void getans()
{
int x=1; int y=n;
for(int i=1;i<=k;i++)
{
cout<<f[x][y]<<endl;
if(g[x][y]==1)
x++;
else
y--;
}
}

int main()
{
init();
for(int l=1;l<=n-1;l++)//长度
for(int i=1;i<=n-l;i++)//起点
{
int j=i+l;//终点
int x=get(i+1,j);//求出上次
int y=get(i,j-1);//的最大值
if(x+a[i]>y+a[j])
{
f[i][j]=x+a[i];
g[i][j]=1;
}
else
{
f[i][j]=y+a[j];
g[i][j]=2;
}
}
getans();
return 0;
}

Copy
0

ljt12138 LV 10 @ 5 年前
还是挺有意思的一道题。
用dp做敌对搜索的思路很巧妙！

0

prince_hao LV 10 @ 11 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

第一次忘记限制下标了结果是WA...

0

voyagec2 LV 10 @ 12 年前
原来如此..

0

ShingRay LV 10 @ 12 年前
opt[i][j] 表示对于 i~j，当前面临选择的同学最大取得的和

有两种选法，选 i 和选 j

pre[i][j]: 面临 i~j 时最优选择方案， 0:选i；1:选j

若选 i

x, y, kk = i+1, j, k-1

while kk > 0:

__|_if pre[x][y] == 0: x += 1

__|_else: y -= 1

___|_kk -= 1

return opt[x][y] + a[i]

选 j 类似

0

jacklv LV 10 @ 12 年前
这题虽然破百了，但是我认为还是值得一写（后悔当初99人的时候没挤一下）

先倒着动规求出f表示某个人取时可以取到的最大值。这个时候还是要做个函数比较方便吧，这个状态是和它倒退k-1步有关的，因为别人还要取。用g表示在面对i到j的数列时取i则g=1 else g=2 ，g的处理对倒退k-1步和最后求每个人取到的数也是有关的

t1=back(i+1,j); t2=back(i,j-1);

if t1+a[i]>t2+a[j] then

begin

f=t1+a[i];

g:=1;

end else ...

最后对于每个人若是他的回合，他面对的数列是i~j

则用g去判断他是取i优还是取j优

总的算法复杂度是（n*n*k）吧

还是过的去的

0

yzl609271536 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 494ms

├ 测试数据 02：答案正确... 447ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1538ms

第100个

这题应该归到DP

0

陈亮宇 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 711ms

├ 测试数据 02：答案正确... 618ms

├ 测试数据 03：答案正确... 306ms

├ 测试数据 04：答案正确... 508ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2143ms

啊蛤蛤 虽然 时间比较慢

此题 第99个AC 的人~

~ AC ~ 100 ~ 题庆

100/321(31%) 　

通过 　　99人

调试了好久 原来是动态规划 。。。 枚举边界问题啊！

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 338ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1116ms

e开头的那个评测机

好了些

0

TLD LV 10 @ 12 年前
其实用个结构体做个返回值就可以了

0

怪盗~基德 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

这时间还真不爽，动规题就该秒杀的。。。。。。

0

mike_nzk LV 10 @ 12 年前
这种沙茶题还3次AC...太弱了...

0

LV 0 @ 12 年前
大牛说的没错，因为每次都保留了决策，做的时候往前推k-1步就知道取i优还是取j优了。

贴下主过程～

但我这样做暴慢～～～，再推k步(back函数）的时候能否优化呢？

for l:=2 to n do

begin

for i:=1 to n-l+1 do

begin

j:=i+l-1;

k1:=back(i+1,j);

k2:=back(i,j-1);

if k1+p[i]>k2+p[j] then begin

f:=k1+p[i];

g:=1;

end

else begin

f:=k2+p[j];

g:=2;

end;

end;

end;

0

k103701 LV 10 @ 13 年前
编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

一个地方改了3遍,从p

0

notblack LV 10 @ 13 年前
样例有什么意义..............

0

junlonely LV 7 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜whqlsc牛牛。！~

0

dengailing LV 3 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多亏了楼上的牛啊。。。。。。。。。。。。。。。

清哥加油！！！！！！！！~~~~~~~~~~~~~~~~

0

FancyMouse LV 3 @ 14 年前
记录状态转移的时候只能逆推（因为某个状态顺推可能有两解）

补充一句……case4我有理由怀疑输入数据少了一个数。即in文件里只有999个数。

大多数人都把变量设为全局变量，因此默认为0——这也是标程默认的，因此以前没人发现这个问题- -

所以，如果是把数据输入局部变量的话，请不要忘记清0。。。

0

zyz915 LV 8 @ 14 年前
唔,总算,想了好久的DP啊...

0

gamejifan LV 7 @ 15 年前
本人主要功绩就是把这题通过率拉下来一个百分点。

我靠。。我只不过DP的时候用了它80MB的内存就说我溢出了，害得我只能用滚动数组

0

thebeet LV 3 @ 15 年前
此题其实和１２０２差不多．．．

做决策的时候　就是多往前面推K步

1 2 下一页 › 末页 »
Advanced Selection
查看题目
递交
讨论
题解
信息
ID1207递交 Accepted难度4分类点击显示标签(无)递交数197我的递交数1已通过79通过率40%被复制3上传者 lolanv
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

0

ljt12138 LV 10 @ 5 年前
还是挺有意思的一道题。
用dp做敌对搜索的思路很巧妙！

0

prince_hao LV 10 @ 11 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

第一次忘记限制下标了结果是WA...

0

voyagec2 LV 10 @ 12 年前
原来如此..

0

ShingRay LV 10 @ 12 年前
opt[i][j] 表示对于 i~j，当前面临选择的同学最大取得的和

有两种选法，选 i 和选 j

pre[i][j]: 面临 i~j 时最优选择方案， 0:选i；1:选j

若选 i

x, y, kk = i+1, j, k-1

while kk > 0:

__|_if pre[x][y] == 0: x += 1

__|_else: y -= 1

___|_kk -= 1

return opt[x][y] + a[i]

选 j 类似

0

jacklv LV 10 @ 12 年前
这题虽然破百了，但是我认为还是值得一写（后悔当初99人的时候没挤一下）

先倒着动规求出f表示某个人取时可以取到的最大值。这个时候还是要做个函数比较方便吧，这个状态是和它倒退k-1步有关的，因为别人还要取。用g表示在面对i到j的数列时取i则g=1 else g=2 ，g的处理对倒退k-1步和最后求每个人取到的数也是有关的

t1=back(i+1,j); t2=back(i,j-1);

if t1+a[i]>t2+a[j] then

begin

f=t1+a[i];

g:=1;

end else ...

最后对于每个人若是他的回合，他面对的数列是i~j

则用g去判断他是取i优还是取j优

总的算法复杂度是（n*n*k）吧

还是过的去的

0

yzl609271536 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 494ms

├ 测试数据 02：答案正确... 447ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1538ms

第100个

这题应该归到DP

0

陈亮宇 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 711ms

├ 测试数据 02：答案正确... 618ms

├ 测试数据 03：答案正确... 306ms

├ 测试数据 04：答案正确... 508ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2143ms

啊蛤蛤 虽然 时间比较慢

此题 第99个AC 的人~

~ AC ~ 100 ~ 题庆

100/321(31%) 　

通过 　　99人

调试了好久 原来是动态规划 。。。 枚举边界问题啊！

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 338ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1116ms

e开头的那个评测机

好了些

0

TLD LV 10 @ 12 年前
其实用个结构体做个返回值就可以了

0

怪盗~基德 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

这时间还真不爽，动规题就该秒杀的。。。。。。

0

mike_nzk LV 10 @ 12 年前
这种沙茶题还3次AC...太弱了...

0

LV 0 @ 12 年前
大牛说的没错，因为每次都保留了决策，做的时候往前推k-1步就知道取i优还是取j优了。

贴下主过程～

但我这样做暴慢～～～，再推k步(back函数）的时候能否优化呢？

for l:=2 to n do

begin

for i:=1 to n-l+1 do

begin

j:=i+l-1;

k1:=back(i+1,j);

k2:=back(i,j-1);

if k1+p[i]>k2+p[j] then begin

f:=k1+p[i];

g:=1;

end

else begin

f:=k2+p[j];

g:=2;

end;

end;

end;

0

k103701 LV 10 @ 13 年前
编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

一个地方改了3遍,从p

0

notblack LV 10 @ 13 年前
样例有什么意义..............

0

junlonely LV 7 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜whqlsc牛牛。！~

0

dengailing LV 3 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多亏了楼上的牛啊。。。。。。。。。。。。。。。

清哥加油！！！！！！！！~~~~~~~~~~~~~~~~

0

FancyMouse LV 3 @ 14 年前
记录状态转移的时候只能逆推（因为某个状态顺推可能有两解）

补充一句……case4我有理由怀疑输入数据少了一个数。即in文件里只有999个数。

大多数人都把变量设为全局变量，因此默认为0——这也是标程默认的，因此以前没人发现这个问题- -

所以，如果是把数据输入局部变量的话，请不要忘记清0。。。

0

zyz915 LV 8 @ 14 年前
唔,总算,想了好久的DP啊...

1 2 下一页 › 末页 »
Advanced Selection
查看题目
递交
讨论
题解
信息
ID1207递交 Accepted难度4分类点击显示标签(无)递交数197我的递交数1已通过79通过率40%被复制3上传者 lolanv
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / Advanced Selection /
题解
25 条题解
0
real_hdsy_gyz LV 0
发表您的题解
2

PowderHan LV 10 @ 4 年前
/*
一道不是很难的动态规划 rp竟然这么高
但是的确很考验思维能力的博弈题
嗯和那个啥P1202有点像(一类) 先去做通P1202
嗯状态是一样的
f[i,j]表示[i,j]中的最大值，但注意只存一个人的
首先需要注意到一个性质：
当确定了哪段[i,j]之后，最后哪个人拿数（i或者j）是确定的，
因此枚举拿i还是拿j，那么哪个更加优呢？
我们可以给每个f[I,j]存一个g[I,j]表示决策，然后往前推k步就行了
即设f[i,j]表示i到j轮到的人能取的最大值
g[i,j]=1表示取i，g[i,j]=2表示取j那么
f[i,j]=max(a[i]+get(i+1，j),a[j]+get(i,j-1))（倒着取）
get函数是用来求上次此人取得的最大值
即我们可以看到k个人实际上是轮流选择这个最优解的
那么比如第x个人 我们枚举他是取左边还是右边
那我们肯定是要考虑到我们要有
a[i]+(选了a[i]后可以达到的最大值)和a[j]+(选了a[j]后的最大值)要取最大值
那么我们怎么得到选了a[i]或a[j]后可以达到的最大值呢？
我们已经用g[i][j]记录了做[i,j]这个区间决策的时候是选取左边还是右边
所以我们就向前推k-1步 即k-1次取数就是上一轮这个人的时候选取得到的最大值
和1202一样我们的每一个决策都是从一个比它短的区间递推而来
所以我们肯定在[i-1,j]或者[i,j-1]中的所有需要的f[][]和g[][]都已经球出来了
所以我们在[i-1][j]和[i,j-1]中推一遍
仔细考虑这个递推的过程
我们看一直将这个区间缩短 如果g[x][y]==1说明这一个区间最优取的是x
则转换为了[x-1,y]中的问题 x--
同理g[x][y]==2 则y--
那么就有两种情况了，这个人是第一次选数字 那么肯定推不到他上次选数的情况
就会出现x>y了 如果没有出现这种情况 那么我们在循环k-1次后
得到的新的f[x][y]一定就是他上次选数之后的最优解了
所以我们就可以根据情况返回0或者f[x][y]
这个函数很重要考虑到了一种DP递推的思路
至于输出答案
我们就按照f[][]和g[][]走一遍
当走完k个人的时候 肯定就将每个人的最优解得出来了
好题 锻炼思维了
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1002;
int a[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int n,k;

void init()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],g[i][i]=1,f[i][i]=a[i];
}

int get(int x,int y)//求上次此人取得的最大和
{
for(int i=1;i<=k-1;i++)
if(x>y)
break;
else if(g[x][y]==1)
x++;
else
y--;
if(x<=y)

return f[x][y];
else
return 0;
}

void getans()
{
int x=1; int y=n;
for(int i=1;i<=k;i++)
{
cout<<f[x][y]<<endl;
if(g[x][y]==1)
x++;
else
y--;
}
}

int main()
{
init();
for(int l=1;l<=n-1;l++)//长度
for(int i=1;i<=n-l;i++)//起点
{
int j=i+l;//终点
int x=get(i+1,j);//求出上次
int y=get(i,j-1);//的最大值
if(x+a[i]>y+a[j])
{
f[i][j]=x+a[i];
g[i][j]=1;
}
else
{
f[i][j]=y+a[j];
g[i][j]=2;
}
}
getans();
return 0;
}

Copy
0

real_hdsy_gyz LV 0 @ 26 秒前

艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / Advanced Selection /
题解
24 条题解
0
real_hdsy_gyz LV 0
艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
​

​
​
​
​

2

PowderHan LV 10 @ 4 年前
/*
一道不是很难的动态规划 rp竟然这么高
但是的确很考验思维能力的博弈题
嗯和那个啥P1202有点像(一类) 先去做通P1202
嗯状态是一样的
f[i,j]表示[i,j]中的最大值，但注意只存一个人的
首先需要注意到一个性质：
当确定了哪段[i,j]之后，最后哪个人拿数（i或者j）是确定的，
因此枚举拿i还是拿j，那么哪个更加优呢？
我们可以给每个f[I,j]存一个g[I,j]表示决策，然后往前推k步就行了
即设f[i,j]表示i到j轮到的人能取的最大值
g[i,j]=1表示取i，g[i,j]=2表示取j那么
f[i,j]=max(a[i]+get(i+1，j),a[j]+get(i,j-1))（倒着取）
get函数是用来求上次此人取得的最大值
即我们可以看到k个人实际上是轮流选择这个最优解的
那么比如第x个人 我们枚举他是取左边还是右边
那我们肯定是要考虑到我们要有
a[i]+(选了a[i]后可以达到的最大值)和a[j]+(选了a[j]后的最大值)要取最大值
那么我们怎么得到选了a[i]或a[j]后可以达到的最大值呢？
我们已经用g[i][j]记录了做[i,j]这个区间决策的时候是选取左边还是右边
所以我们就向前推k-1步 即k-1次取数就是上一轮这个人的时候选取得到的最大值
和1202一样我们的每一个决策都是从一个比它短的区间递推而来
所以我们肯定在[i-1,j]或者[i,j-1]中的所有需要的f[][]和g[][]都已经球出来了
所以我们在[i-1][j]和[i,j-1]中推一遍
仔细考虑这个递推的过程
我们看一直将这个区间缩短 如果g[x][y]==1说明这一个区间最优取的是x
则转换为了[x-1,y]中的问题 x--
同理g[x][y]==2 则y--
那么就有两种情况了，这个人是第一次选数字 那么肯定推不到他上次选数的情况
就会出现x>y了 如果没有出现这种情况 那么我们在循环k-1次后
得到的新的f[x][y]一定就是他上次选数之后的最优解了
所以我们就可以根据情况返回0或者f[x][y]
这个函数很重要考虑到了一种DP递推的思路
至于输出答案
我们就按照f[][]和g[][]走一遍
当走完k个人的时候 肯定就将每个人的最优解得出来了
好题 锻炼思维了
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1002;
int a[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int n,k;

void init()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],g[i][i]=1,f[i][i]=a[i];
}

int get(int x,int y)//求上次此人取得的最大和
{
for(int i=1;i<=k-1;i++)
if(x>y)
break;
else if(g[x][y]==1)
x++;
else
y--;
if(x<=y)

return f[x][y];
else
return 0;
}

void getans()
{
int x=1; int y=n;
for(int i=1;i<=k;i++)
{
cout<<f[x][y]<<endl;
if(g[x][y]==1)
x++;
else
y--;
}
}

int main()
{
init();
for(int l=1;l<=n-1;l++)//长度
for(int i=1;i<=n-l;i++)//起点
{
int j=i+l;//终点
int x=get(i+1,j);//求出上次
int y=get(i,j-1);//的最大值
if(x+a[i]>y+a[j])
{
f[i][j]=x+a[i];
g[i][j]=1;
}
else
{
f[i][j]=y+a[j];
g[i][j]=2;
}
}
getans();
return 0;
}

Copy
0

ljt12138 LV 10 @ 5 年前
还是挺有意思的一道题。
用dp做敌对搜索的思路很巧妙！

0

prince_hao LV 10 @ 11 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

第一次忘记限制下标了结果是WA...

0

voyagec2 LV 10 @ 12 年前
原来如此..

0

ShingRay LV 10 @ 12 年前
opt[i][j] 表示对于 i~j，当前面临选择的同学最大取得的和

有两种选法，选 i 和选 j

pre[i][j]: 面临 i~j 时最优选择方案， 0:选i；1:选j

若选 i

x, y, kk = i+1, j, k-1

while kk > 0:

__|_if pre[x][y] == 0: x += 1

__|_else: y -= 1

___|_kk -= 1

return opt[x][y] + a[i]

选 j 类似

0

jacklv LV 10 @ 12 年前
这题虽然破百了，但是我认为还是值得一写（后悔当初99人的时候没挤一下）

先倒着动规求出f表示某个人取时可以取到的最大值。这个时候还是要做个函数比较方便吧，这个状态是和它倒退k-1步有关的，因为别人还要取。用g表示在面对i到j的数列时取i则g=1 else g=2 ，g的处理对倒退k-1步和最后求每个人取到的数也是有关的

t1=back(i+1,j); t2=back(i,j-1);

if t1+a[i]>t2+a[j] then

begin

f=t1+a[i];

g:=1;

end else ...

最后对于每个人若是他的回合，他面对的数列是i~j

则用g去判断他是取i优还是取j优

总的算法复杂度是（n*n*k）吧

还是过的去的

0

yzl609271536 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 494ms

├ 测试数据 02：答案正确... 447ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1538ms

第100个

这题应该归到DP

0

陈亮宇 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 711ms

├ 测试数据 02：答案正确... 618ms

├ 测试数据 03：答案正确... 306ms

├ 测试数据 04：答案正确... 508ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2143ms

啊蛤蛤 虽然 时间比较慢

此题 第99个AC 的人~

~ AC ~ 100 ~ 题庆

100/321(31%) 　

通过 　　99人

调试了好久 原来是动态规划 。。。 枚举边界问题啊！

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 338ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1116ms

e开头的那个评测机

好了些

0

TLD LV 10 @ 12 年前
其实用个结构体做个返回值就可以了

0

怪盗~基德 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

这时间还真不爽，动规题就该秒杀的。。。。。。

0

mike_nzk LV 10 @ 12 年前
这种沙茶题还3次AC...太弱了...

0

LV 0 @ 12 年前
大牛说的没错，因为每次都保留了决策，做的时候往前推k-1步就知道取i优还是取j优了。

贴下主过程～

但我这样做暴慢～～～，再推k步(back函数）的时候能否优化呢？

for l:=2 to n do

begin

for i:=1 to n-l+1 do

begin

j:=i+l-1;

k1:=back(i+1,j);

k2:=back(i,j-1);

if k1+p[i]>k2+p[j] then begin

f:=k1+p[i];

g:=1;

end

else begin

f:=k2+p[j];

g:=2;

end;

end;

end;

0

k103701 LV 10 @ 13 年前
编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

一个地方改了3遍,从p

0

notblack LV 10 @ 13 年前
样例有什么意义..............

0

junlonely LV 7 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜whqlsc牛牛。！~

0

dengailing LV 3 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多亏了楼上的牛啊。。。。。。。。。。。。。。。

清哥加油！！！！！！！！~~~~~~~~~~~~~~~~

0

FancyMouse LV 3 @ 14 年前
记录状态转移的时候只能逆推（因为某个状态顺推可能有两解）

补充一句……case4我有理由怀疑输入数据少了一个数。即in文件里只有999个数。

大多数人都把变量设为全局变量，因此默认为0——这也是标程默认的，因此以前没人发现这个问题- -

所以，如果是把数据输入局部变量的话，请不要忘记清0。。。

0

zyz915 LV 8 @ 14 年前
唔,总算,想了好久的DP啊...

0

gamejifan LV 7 @ 15 年前
本人主要功绩就是把这题通过率拉下来一个百分点。

我靠。。我只不过DP的时候用了它80MB的内存就说我溢出了，害得我只能用滚动数组

0

thebeet LV 3 @ 15 年前
此题其实和１２０２差不多．．．

做决策的时候　就是多往前面推K步

1 2 下一页 › 末页 »
Advanced Selection
查看题目
递交
讨论
题解
信息
ID1207递交 Accepted难度4分类点击显示标签(无)递交数197我的递交数1已通过79通过率40%被复制3上传者 lolanv
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

0

ljt12138 LV 10 @ 5 年前
还是挺有意思的一道题。
用dp做敌对搜索的思路很巧妙！

0

prince_hao LV 10 @ 11 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

第一次忘记限制下标了结果是WA...

0

voyagec2 LV 10 @ 12 年前
原来如此..

0

ShingRay LV 10 @ 12 年前
opt[i][j] 表示对于 i~j，当前面临选择的同学最大取得的和

有两种选法，选 i 和选 j

pre[i][j]: 面临 i~j 时最优选择方案， 0:选i；1:选j

若选 i

x, y, kk = i+1, j, k-1

while kk > 0:

__|_if pre[x][y] == 0: x += 1

__|_else: y -= 1

___|_kk -= 1

return opt[x][y] + a[i]

选 j 类似

0

jacklv LV 10 @ 12 年前
这题虽然破百了，但是我认为还是值得一写（后悔当初99人的时候没挤一下）

先倒着动规求出f表示某个人取时可以取到的最大值。这个时候还是要做个函数比较方便吧，这个状态是和它倒退k-1步有关的，因为别人还要取。用g表示在面对i到j的数列时取i则g=1 else g=2 ，g的处理对倒退k-1步和最后求每个人取到的数也是有关的

t1=back(i+1,j); t2=back(i,j-1);

if t1+a[i]>t2+a[j] then

begin

f=t1+a[i];

g:=1;

end else ...

最后对于每个人若是他的回合，他面对的数列是i~j

则用g去判断他是取i优还是取j优

总的算法复杂度是（n*n*k）吧

还是过的去的

0

yzl609271536 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 494ms

├ 测试数据 02：答案正确... 447ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1538ms

第100个

这题应该归到DP

0

陈亮宇 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 711ms

├ 测试数据 02：答案正确... 618ms

├ 测试数据 03：答案正确... 306ms

├ 测试数据 04：答案正确... 508ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2143ms

啊蛤蛤 虽然 时间比较慢

此题 第99个AC 的人~

~ AC ~ 100 ~ 题庆

100/321(31%) 　

通过 　　99人

调试了好久 原来是动态规划 。。。 枚举边界问题啊！

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 338ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1116ms

e开头的那个评测机

好了些

0

TLD LV 10 @ 12 年前
其实用个结构体做个返回值就可以了

0

怪盗~基德 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

这时间还真不爽，动规题就该秒杀的。。。。。。

0

mike_nzk LV 10 @ 12 年前
这种沙茶题还3次AC...太弱了...

0

LV 0 @ 12 年前
大牛说的没错，因为每次都保留了决策，做的时候往前推k-1步就知道取i优还是取j优了。

贴下主过程～

但我这样做暴慢～～～，再推k步(back函数）的时候能否优化呢？

for l:=2 to n do

begin

for i:=1 to n-l+1 do

begin

j:=i+l-1;

k1:=back(i+1,j);

k2:=back(i,j-1);

if k1+p[i]>k2+p[j] then begin

f:=k1+p[i];

g:=1;

end

else begin

f:=k2+p[j];

g:=2;

end;

end;

end;

0

k103701 LV 10 @ 13 年前
编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

一个地方改了3遍,从p

0

notblack LV 10 @ 13 年前
样例有什么意义..............

0

junlonely LV 7 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜whqlsc牛牛。！~

0

dengailing LV 3 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多亏了楼上的牛啊。。。。。。。。。。。。。。。

清哥加油！！！！！！！！~~~~~~~~~~~~~~~~

0

FancyMouse LV 3 @ 14 年前
记录状态转移的时候只能逆推（因为某个状态顺推可能有两解）

补充一句……case4我有理由怀疑输入数据少了一个数。即in文件里只有999个数。

大多数人都把变量设为全局变量，因此默认为0——这也是标程默认的，因此以前没人发现这个问题- -

所以，如果是把数据输入局部变量的话，请不要忘记清0。。。

0

zyz915 LV 8 @ 14 年前
唔,总算,想了好久的DP啊...

0

gamejifan LV 7 @ 15 年前
本人主要功绩就是把这题通过率拉下来一个百分点。

我靠。。我只不过DP的时候用了它80MB的内存就说我溢出了，害得我只能用滚动数组

1 2 下一页 › 末页 »
Advanced Selection
查看题目
递交
讨论
题解
信息
ID1207递交 Accepted难度4分类点击显示标签(无)递交数197我的递交数1已通过79通过率40%被复制3上传者 lolanv
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / Advanced Selection /
题解
24 条题解
0
real_hdsy_gyz LV 0
艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

艾斯芬尼发v发疯你敢惹我认为你是个粗人你认为你传给我i高恩额色偶分嗡嗡呢sins v发动机扫地发动机安抚CEO我过热i给共i光荣而qi如果ghtwe 我和人感情问题让各位他还认为热wt和人wthrwherrwhtrjwherqwthh让他为日后温热确认以前和人签合同和热情而他认为节目我却NBC欸跑去微软承诺他如果拼凑奇怪么微软传感器抛开网通IP从为何惧怕公开从我个人狂热物品给公平问题后i我今儿哦苹果欧派股票进而我i孤家寡人拍屁股公共i我今儿放弃过认为认识个个武功购物i给！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
​

​

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

​
​
​

2

PowderHan LV 10 @ 4 年前
/*
一道不是很难的动态规划 rp竟然这么高
但是的确很考验思维能力的博弈题
嗯和那个啥P1202有点像(一类) 先去做通P1202
嗯状态是一样的
f[i,j]表示[i,j]中的最大值，但注意只存一个人的
首先需要注意到一个性质：
当确定了哪段[i,j]之后，最后哪个人拿数（i或者j）是确定的，
因此枚举拿i还是拿j，那么哪个更加优呢？
我们可以给每个f[I,j]存一个g[I,j]表示决策，然后往前推k步就行了
即设f[i,j]表示i到j轮到的人能取的最大值
g[i,j]=1表示取i，g[i,j]=2表示取j那么
f[i,j]=max(a[i]+get(i+1，j),a[j]+get(i,j-1))（倒着取）
get函数是用来求上次此人取得的最大值
即我们可以看到k个人实际上是轮流选择这个最优解的
那么比如第x个人 我们枚举他是取左边还是右边
那我们肯定是要考虑到我们要有
a[i]+(选了a[i]后可以达到的最大值)和a[j]+(选了a[j]后的最大值)要取最大值
那么我们怎么得到选了a[i]或a[j]后可以达到的最大值呢？
我们已经用g[i][j]记录了做[i,j]这个区间决策的时候是选取左边还是右边
所以我们就向前推k-1步 即k-1次取数就是上一轮这个人的时候选取得到的最大值
和1202一样我们的每一个决策都是从一个比它短的区间递推而来
所以我们肯定在[i-1,j]或者[i,j-1]中的所有需要的f[][]和g[][]都已经球出来了
所以我们在[i-1][j]和[i,j-1]中推一遍
仔细考虑这个递推的过程
我们看一直将这个区间缩短 如果g[x][y]==1说明这一个区间最优取的是x
则转换为了[x-1,y]中的问题 x--
同理g[x][y]==2 则y--
那么就有两种情况了，这个人是第一次选数字 那么肯定推不到他上次选数的情况
就会出现x>y了 如果没有出现这种情况 那么我们在循环k-1次后
得到的新的f[x][y]一定就是他上次选数之后的最优解了
所以我们就可以根据情况返回0或者f[x][y]
这个函数很重要考虑到了一种DP递推的思路
至于输出答案
我们就按照f[][]和g[][]走一遍
当走完k个人的时候 肯定就将每个人的最优解得出来了
好题 锻炼思维了
OTZ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1002;
int a[MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];
int n,k;

void init()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],g[i][i]=1,f[i][i]=a[i];
}

int get(int x,int y)//求上次此人取得的最大和
{
for(int i=1;i<=k-1;i++)
if(x>y)
break;
else if(g[x][y]==1)
x++;
else
y--;
if(x<=y)

return f[x][y];
else
return 0;
}

void getans()
{
int x=1; int y=n;
for(int i=1;i<=k;i++)
{
cout<<f[x][y]<<endl;
if(g[x][y]==1)
x++;
else
y--;
}
}

int main()
{
init();
for(int l=1;l<=n-1;l++)//长度
for(int i=1;i<=n-l;i++)//起点
{
int j=i+l;//终点
int x=get(i+1,j);//求出上次
int y=get(i,j-1);//的最大值
if(x+a[i]>y+a[j])
{
f[i][j]=x+a[i];
g[i][j]=1;
}
else
{
f[i][j]=y+a[j];
g[i][j]=2;
}
}
getans();
return 0;
}

Copy
0

ljt12138 LV 10 @ 5 年前
还是挺有意思的一道题。
用dp做敌对搜索的思路很巧妙！

0

prince_hao LV 10 @ 11 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

第一次忘记限制下标了结果是WA...

0

voyagec2 LV 10 @ 12 年前
原来如此..

0

ShingRay LV 10 @ 12 年前
opt[i][j] 表示对于 i~j，当前面临选择的同学最大取得的和

有两种选法，选 i 和选 j

pre[i][j]: 面临 i~j 时最优选择方案， 0:选i；1:选j

若选 i

x, y, kk = i+1, j, k-1

while kk > 0:

__|_if pre[x][y] == 0: x += 1

__|_else: y -= 1

___|_kk -= 1

return opt[x][y] + a[i]

选 j 类似

0

jacklv LV 10 @ 12 年前
这题虽然破百了，但是我认为还是值得一写（后悔当初99人的时候没挤一下）

先倒着动规求出f表示某个人取时可以取到的最大值。这个时候还是要做个函数比较方便吧，这个状态是和它倒退k-1步有关的，因为别人还要取。用g表示在面对i到j的数列时取i则g=1 else g=2 ，g的处理对倒退k-1步和最后求每个人取到的数也是有关的

t1=back(i+1,j); t2=back(i,j-1);

if t1+a[i]>t2+a[j] then

begin

f=t1+a[i];

g:=1;

end else ...

最后对于每个人若是他的回合，他面对的数列是i~j

则用g去判断他是取i优还是取j优

总的算法复杂度是（n*n*k）吧

还是过的去的

0

yzl609271536 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 494ms

├ 测试数据 02：答案正确... 447ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1538ms

第100个

这题应该归到DP

0

陈亮宇 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 711ms

├ 测试数据 02：答案正确... 618ms

├ 测试数据 03：答案正确... 306ms

├ 测试数据 04：答案正确... 508ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2143ms

啊蛤蛤 虽然 时间比较慢

此题 第99个AC 的人~

~ AC ~ 100 ~ 题庆

100/321(31%) 　

通过 　　99人

调试了好久 原来是动态规划 。。。 枚举边界问题啊！

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 338ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1116ms

e开头的那个评测机

好了些

0

TLD LV 10 @ 12 年前
其实用个结构体做个返回值就可以了

0

怪盗~基德 LV 10 @ 12 年前
编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

这时间还真不爽，动规题就该秒杀的。。。。。。

0

mike_nzk LV 10 @ 12 年前
这种沙茶题还3次AC...太弱了...

0

LV 0 @ 12 年前
大牛说的没错，因为每次都保留了决策，做的时候往前推k-1步就知道取i优还是取j优了。

贴下主过程～

但我这样做暴慢～～～，再推k步(back函数）的时候能否优化呢？

for l:=2 to n do

begin

for i:=1 to n-l+1 do

begin

j:=i+l-1;

k1:=back(i+1,j);

k2:=back(i,j-1);

if k1+p[i]>k2+p[j] then begin

f:=k1+p[i];

g:=1;

end

else begin

f:=k2+p[j];

g:=2;

end;

end;

end;

0

k103701 LV 10 @ 13 年前
编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

一个地方改了3遍,从p

0

notblack LV 10 @ 13 年前
样例有什么意义..............

0

junlonely LV 7 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜whqlsc牛牛。！~

0

dengailing LV 3 @ 14 年前
编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多亏了楼上的牛啊。。。。。。。。。。。。。。。

清哥加油！！！！！！！！~~~~~~~~~~~~~~~~

0

FancyMouse LV 3 @ 14 年前
记录状态转移的时候只能逆推（因为某个状态顺推可能有两解）

补充一句……case4我有理由怀疑输入数据少了一个数。即in文件里只有999个数。

大多数人都把变量设为全局变量，因此默认为0——这也是标程默认的，因此以前没人发现这个问题- -

所以，如果是把数据输入局部变量的话，请不要忘记清0。。。

0

zyz915 LV 8 @ 14 年前
唔,总算,想了好久的DP啊...

0

gamejifan LV 7 @ 15 年前
本人主要功绩就是把这题通过率拉下来一个百分点。

我靠。。我只不过DP的时候用了它80MB的内存就说我溢出了，害得我只能用滚动数组

0

thebeet LV 3 @ 15 年前
此题其实和１２０２差不多．．．

做决策的时候　就是多往前面推K步

1 2 下一页 › 末页 »
Advanced Selection
查看题目
递交
讨论
题解
信息
ID1207递交 Accepted难度4分类点击显示标签(无)递交数197我的递交数1已通过79通过率40%被复制3上传者 lolanv
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

还是挺有意思的一道题。
用dp做敌对搜索的思路很巧妙！

编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 103ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

第一次忘记限制下标了结果是WA...

原来如此..

opt[i][j] 表示对于 i~j，当前面临选择的同学最大取得的和

有两种选法，选 i 和选 j

pre[i][j]: 面临 i~j 时最优选择方案， 0:选i；1:选j

若选 i

x, y, kk = i+1, j, k-1

while kk > 0:

__|_if pre[x][y] == 0: x += 1

__|_else: y -= 1

___|_kk -= 1

return opt[x][y] + a[i]

选 j 类似

这题虽然破百了，但是我认为还是值得一写（后悔当初99人的时候没挤一下）

先倒着动规求出f表示某个人取时可以取到的最大值。这个时候还是要做个函数比较方便吧，这个状态是和它倒退k-1步有关的，因为别人还要取。用g表示在面对i到j的数列时取i则g=1 else g=2 ，g的处理对倒退k-1步和最后求每个人取到的数也是有关的

t1=back(i+1,j); t2=back(i,j-1);

if t1+a[i]>t2+a[j] then

begin

f=t1+a[i];

g:=1;

end else ...

最后对于每个人若是他的回合，他面对的数列是i~j

则用g去判断他是取i优还是取j优

总的算法复杂度是（n*n*k）吧

还是过的去的

编译通过...

├ 测试数据 01：答案正确... 494ms

├ 测试数据 02：答案正确... 447ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 400ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1538ms

第100个

这题应该归到DP

编译通过...

├ 测试数据 01：答案正确... 711ms

├ 测试数据 02：答案正确... 618ms

├ 测试数据 03：答案正确... 306ms

├ 测试数据 04：答案正确... 508ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2143ms

啊蛤蛤 虽然 时间比较慢

此题 第99个AC 的人~

~ AC ~ 100 ~ 题庆

100/321(31%) 　

通过 　　99人

调试了好久 原来是动态规划 。。。 枚举边界问题啊！

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 338ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 275ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1116ms

e开头的那个评测机

好了些

其实用个结构体做个返回值就可以了

编译通过...

├ 测试数据 01：答案正确... 134ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

这时间还真不爽，动规题就该秒杀的。。。。。。

这种沙茶题还3次AC...太弱了...

大牛说的没错，因为每次都保留了决策，做的时候往前推k-1步就知道取i优还是取j优了。

贴下主过程～

但我这样做暴慢～～～，再推k步(back函数）的时候能否优化呢？

for l:=2 to n do

begin

for i:=1 to n-l+1 do

begin

j:=i+l-1;

k1:=back(i+1,j);

k2:=back(i,j-1);

if k1+p[i]>k2+p[j] then begin

f:=k1+p[i];

g:=1;

end

else begin

f:=k2+p[j];

g:=2;

end;

end;

end;

编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

一个地方改了3遍,从p

样例有什么意义..............

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜whqlsc牛牛。！~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

多亏了楼上的牛啊。。。。。。。。。。。。。。。

清哥加油！！！！！！！！~~~~~~~~~~~~~~~~