恨自己奥林匹克没认真学 呵呵～模型化以后是这样的
有一个线性表 （可能很长 a[i]>0 ）
比如 4 2 5 7 8 3 2 9现在寻找n个位置(假设n=2) 假设n1=4 则将第4个位置置零 周围数依次减去3 2 1(类似一共辐射了三个数字 依次减弱 减到０为止） 如果一个位置的数被两次或更多次辐射到 则取减的最多的一次（这个是关键）据上面的例子：
n=2
n1=4 n2=5则
a[1]=a[1]-1=3
a[2]=a[2]-2=0
a[3]=a[3]-3=2
a[4]=0
a[5]=0
a[6]被a[4]辐射-2 被a[5]辐射-3 所以取a[6]=a[6]-3=0
类似 a[7]=a[7]-2=0 a[8]=a[8]-1=8这样数列就成了 3 0 2 0 0 0 8输入原始数列及n 现在要求寻找n个“辐射点”位置 使最后得到的数列中和最小!
不能用搜索！因为实际应用时线性表很长～～～1000个数据选10个n搜索绝对不行的，，除非有什么好的优化方法问问大家有没有写什么好的方法 不一定要求出最优解 能求出一个较优解也行（我准备用贪心法求较优解 但是这样求出来的有时候和最优解差别极大～不好用）
有一个线性表 （可能很长 a[i]>0 ）
比如 4 2 5 7 8 3 2 9现在寻找n个位置(假设n=2) 假设n1=4 则将第4个位置置零 周围数依次减去3 2 1(类似一共辐射了三个数字 依次减弱 减到０为止） 如果一个位置的数被两次或更多次辐射到 则取减的最多的一次（这个是关键）据上面的例子：
n=2
n1=4 n2=5则
a[1]=a[1]-1=3
a[2]=a[2]-2=0
a[3]=a[3]-3=2
a[4]=0
a[5]=0
a[6]被a[4]辐射-2 被a[5]辐射-3 所以取a[6]=a[6]-3=0
类似 a[7]=a[7]-2=0 a[8]=a[8]-1=8这样数列就成了 3 0 2 0 0 0 8输入原始数列及n 现在要求寻找n个“辐射点”位置 使最后得到的数列中和最小!
不能用搜索！因为实际应用时线性表很长～～～1000个数据选10个n搜索绝对不行的，，除非有什么好的优化方法问问大家有没有写什么好的方法 不一定要求出最优解 能求出一个较优解也行（我准备用贪心法求较优解 但是这样求出来的有时候和最优解差别极大～不好用）
n1=4 n2=5
就是有说4 5两个辐射点
建议楼主去www.mydrs.org问那群高中生，不要不好意思……
问下楼主,你是在哪个online judge上看到这题目的,我也想去做做.
但纯dp是不行的,假设已经有一个最优值了,那他的子空间是最优的吗?不一定是!
如果用搜的,状态空间太大一共是C(10,1000).
想想有什么规律否?????
...........................
感觉象是np题.
数组是一定的,总合也是一定的.
每个辐射最多可以减少a[X]+Y,(0<=Y<=12)的值.
结果是求(a[x1]+a[x2]+....+a[xn])+(y1+y2+...+yn)最大.
难点是y的值会受到x自身和相近xn的位置而变化.所以y的方程比较复杂.
先考虑特殊情况,如果x1 >= x2+y的话,就选择X1该点,如果你选择的10个点,相对与其他个点都满足这个条件,那么肯定是最优值.可惜这个特殊情况没什么用,只是我思考的一个过成.如果是比赛,我可能会放弃这道题目,但在平时,我会尝试去做.
我会用PFS+DP来做,带优先队列的bfs+dp,这里的dp只是存储中间结果用的,目的和优先队列的目的一样,只是减少搜索空间,这里的优先权值你可以设置.如果空间还是太大,就用迭代加深搜索.
这里的数组要建三维.你说用贪心找近似值,我觉得很难证明这个值的近似程度,你说呢.
明天在想想看,要睡了.:)
明天还想不出来,就帮你问问高手看.
1:
if the n*7 > numbercount the broadcast point should scatter too.
2:
if the n*7< numbercount the broadcast point should let the nearby the broadcast point's point dec too much.
{
int len=sizeof(a) / sizeof(n),i,j,findbpcnt=0;
int bpnum[500];//save boradcast point;
bool cansetbp;
if(n*7<len)
{step=7;
for(i=0;i<len;i+=step) /////////////////////////////////////////////
{cansetbp=false
for(j=0;j<3;j++)
{ //search the bp 's first step
if(a[i+j]<j+1)
{break;
}
if(j<3)
{step=3;
}
else
{
step=7;
bpnum[findbpcnt]=i+j;
findbpcnt++;
}
}
if(findbpcnt>=n)
break;
} ////////////////////////////////////////////////////////
i=0;
while(findbpcnt<n && i<len) ////////////////////////////////////
{
if((a[bpnum[i]-1]>a[bpnum[i]-2] && a[bpnum[i]-2]> a[bpnum[i]-3])
)
{
bpnum[findcnt++]=bpnum[i]-1;
}
else // //search the bp 's second step
if (a[bpnum[i]+1]>a[bpnum[i]+2] && a[bpnum[i]+2]> a[bpnum[i]+3])
{
bpnum[findcnt++]=bpnum[i]+1;
}
i++;
} ///////////////////////////////////////////
i=0;
while(findbpcnt<n && i<len) //////////////////////////////////////////////
{
if((a[bpnum[i]-1]>a[bpnum[i]-2] || a[bpnum[i]-2]> a[bpnum[i]-3]) && ! (a[bpnum[i]-1]>a[bpnum[i]-2] && a[bpnum[i]-2]> a[bpnum[i]-3])
)
{
bpnum[findcnt++]=bpnum[i]-1;
}
else
if( (a[bpnum[i]+1]>a[bpnum[i]+2] // //search the bp 's third step
||a[bpnum[i]+2]> a[bpnum[i]+3]) && ! (a[bpnum[i]+1]>a[bpnum[i]+2] && a[bpnum[i]+2]> a[bpnum[i]+3]) )
{
bpnum[findcnt++]=bpnum[i]+1;
}
i++;
} /////////////////////////////////////////
}
else
{
}}
我自己做一个东西的时候遇到的上面的程序暂时还没看
先说说我自己现在的思路（类似动规）1 确定源1
2 for i=1 to count 搜索源2 确保2与已知源中重叠消耗最小！
3 用2的方法寻找n个源也就是一个一个源搜 确保新源的确定造成的浪费最小
我是去年做acm的时候,认识一些高中生的,基本上都是各个省里的尖子,那些高中生太强了,让我惭愧.
楼主也不简单啊,自学成材(引用你QQ里的资料),呵呵,是呀,我见过的高手,几乎都是自学成材的.
最近做工程,想用delphi,以前都用C/C++做的,所以来这里看看,还请多多指教.
我是个菜鸟,半路出家的,今年大三才转读软件,恨自己搞软件太迟了,不能学习,工程,acm全顾,过得很累,我特别羡慕你们,高中就打下这样的基础,到大学里就非常轻松了,而且有这些获奖的背景,将来进
IBM,intel,ms都很有可能.
以前初中没拿过一等至少还是能过NOIP的。。现在很惨别跑题了 讨论上面的题目 谁还有什么更好的办法吗？
上面的题目还需要进一步复杂化 各个辐射源的辐射能力以及每个位置被辐射的时候减少的值也是不一定的 这样考虑的时候还需要更麻烦一点.........有点焦头烂额了
这样的话是没结果的，你不公布规律的话，大家怎么做？
另外辐射源为什么不放在数列中数值最大的位置上呢？
我讲讲我的思路，建立在未复杂化题目之前的：
1，找出数列中数值排名前2N位的数字和位置，一个循环就够了。
2，在这前2N位数字里进行辐射计算，取出里面的辐射最大化数列。
没什么规律的 各个辐射源的辐射能力都外部输入 另外辐射源为什么不放在数列中数值最大的位置上呢？
我想你没有彻底理解题目意思 辐射减小的值=辐射源处的值+辐射源周围元素因辐射减小的值 ,辐射源放在数列中数值最大的位置上就是最简单的贪心法,基本上不能这么考虑
改进一点就是考虑各个辐射减小的值总和来排序 这是改进的贪心法 由于重叠没考虑到 这样的贪心误差也会很大
再改进就是连重叠也考虑进去 这样看起来问题不大 但是也不能确保得出的就是最优或较优解.....暂时只思考到这里