求程序设计答案

第一题：不好意思，没懂你题目的意思，估计是个简单的排序；

第二题：穷举，for循环；

第三题：分成5个三角形，分别用海伦公式求面积，相加；

第四题：经典的贪心，但贪心的策略要想清楚，自己尝试举举反例；

第五题：floyed吧，这个好写啊，虽然dijkstra要快一些；

第六题：高精度乘法；

第七题：深搜应该可以了吧；

第八题：先打好素数表，然后DFS

第九题：经典的动规；

第十题：分治；

其实很多题目在书上都有，我说得比较简单，希望能给你启发

题解(from USACO)

三值排序问题 [IOI 1996]

有一个由N个数值均为1、2或3的数构成的序列（N<= 1000），其值无序，现要求你用最少的交换次数将序列按升序顺序排列。

算法：排序后的序列分为三个部分：排序后应存储1的部分，排序后应存储2的部分和排序后应存储3的部分，贪心排序法应交换尽量多的交换后位置正确的（2，1）、（3，1）和（3，2）数对。当这些数对交换完毕后，再交换进行两次交换后位置正确的（1，2，3）三个数。

分析：很明显，每一次交换都可以改变两个数的位置，若经过一次交换以后，两个数的位置都由错误变为了正确，那么它必定最优。同时我们还可发现，经过两次交换后，我们可以随意改变3个数的位置。那么如果存在三个数恰好为1，2和3，且位置都是错误的，那么进行两次交换使它们位置正确也必定最优。有由于该题具有最优子结构性质，我们的贪心算法成立

程序：

var a:array[1..1000] of integer

f:array[1..3,1..3] of integer

b:array[1..3] of integer

n,i,j,t,p:integer

begin

readln(n)

for i:=1 to n do readln(a[i])

fillchar(f,sizeof(f),0)

for i:=1 to n do inc(b[a[i]])

b[2]:=b[2]+b[1]

b[3]:=n

t:=0

for i:=1 to n do

if i<=b[1] then inc(f[1,a[i]]) else

if i<=b[2] then inc(f[2,a[i]]) else

if i<=b[3] then inc(f[3,a[i]])

for i:=1 to 2 do

for j:=i+1 to 3 do

begin

if f[i,j]>f[j,i] then p:=f[j,i] else p:=f[i,j]

t:=t+p

if f[i,j]-p>=0 then f[i,j]:=f[i,j]-p

if f[j,i]-p>=0 then f[j,i]:=f[j,i]-p

end

t:=t+(f[1,2]+f[1,3]) shl 1

writeln(t)

end.

另外,站长团上有产品团购,便宜有保证

这道题的贪心算法比较容易理解，我就不多说明了，只是提到一下算法思路1、建立数学模型描述问题。我在这里将时间理解成一条直线，上面有若干个点，可能是某些活动的起始时间点，或终止时间点。在具体一下，如果编程来实现的话，将时间抽象成链表数组，数组下标代表其实时间，该下标对应的链表代表在这个时间起始的活动都有哪些，具体参照程序注释。2、问题分解。为了安排更多的活动，那么每次选取占用时间最少的活动就好。那么从一开始就选取结束时间最早的，然后寻找在这个时间点上起始的活动，以此类推就可以找出贪心解。程序代码：#include<stdio.h>

struct inode //自定义的结构体

{

int end //表示结束时间

inode *next//指向下一个节点的指针

}int main()

{

inode start[10001],*pt

int a,b,i,num=0 //num负责计数，i控制循环，a，b输入时候使用

for(i=0i<10001i++) //初始化

{

start[i].next=NULL

}

while(scanf("%d %d",&a,&b)) //输入并建立数据结构

{

if(a==0&&b==0) break

pt=new inode //创建新的节点，然后将该节点插入相应的位置

pt->end=b

pt->next=start[a].next

start[a].next=pt

}

i=0

while(i<10001) //进行贪心算法，i表示当前时间

{

if(start[i].next==NULL)

{

i++ //该时间无活动开始

}

else

{

int temp=10001 //临时变量，存储该链表中最早的终止时间

for(pt=start[i].nextpt!=NULLpt=pt->next)

{

if(pt->end<temp)

{

temp=pt->end

}

}

i=temp //将当前时间设置成前一子问题的终止时间

num++

}

}

printf("%d\n",num) //打印结果

return 0

}代码并不一定是最快速的，但是可以求出贪心解，如果你做的是ACM编程题目，不保证能AC注释我尽力写了，希望对你有帮助。

---