UC知道pascal 动规...
来源：百度知道 编辑：UC知道 时间：2024/05/25 07:00:25
是不是这个不满足后无效性啊？
最佳课题选择
描述 Description
Matrix67要在下个月交给老师n篇论文，论文的内容可以从m个课题中选择。由于课题数有限，Matrix67不得不重复选择一些课题。完成不同课题的论文所花的时间不同。具体地说，对于某个课题i，若Matrix67计划一共写x篇论文，则完成该课题的论文总共需要花费Ai*x^Bi个单位时间（系数Ai和指数Bi均为正整数）。给定与每一个课题相对应的Ai和Bi的值，请帮助Matrix67计算出如何选择论文的课题使得他可以花费最少的时间完成这n篇论文。
输入格式 Input Format
第一行有两个用空格隔开的正整数n和m，分别代表需要完成的论文数和可供选择的课题数。以下m行每行有两个用空格隔开的正整数。其中，第i行的两个数分别代表与第i个课题相对应的时间系数Ai和指数Bi。
对于30%的数据，n<=10,m<=5；
对于100%的数据，n<=200，m<=20，Ai<=100，Bi<=5。
输出格式 Output Format
输出完成n篇论文所需要耗费的最少时间。
样例输入 Sample Input
10 3
2 1
1 2
2 1
样例输出 Sample Output
19
时间限制 Time Limitation
各个测试点1s
注释 Hint
样例说明：
4篇论文选择课题一，5篇论文选择课题三，剩下一篇论文选择课题二，总耗时为2*4^1+1*1^2+2*5^1=8+1+10=19。可以证明，不存在更优的方案使耗时小于19。
我的程序.....
program P1198;
type
re=record
a,b,c:integer;
e
好吧。。。我连蒙带骗全a了。。。2维数组，一组骗分
program 1198;
var
a:array[0..2000,0..2000] of int64;
b,c:array[0..2000] of int64;
i,j,k,l,n,m,x,y:longint;
min:int64;
t:text;
begin
readln(n,m);
for i:=1 to m do
readln(b[i],c[i]);
for i:=1 to n do
a[1,i]:=b[1]*trunc(exp(c[1]*ln(i)));
for i:=2 to m do
for j:=0 to n do
begin
for k:=0 to j do
if k=0 then min:=a[i-1,j] else
if b[i]*round(exp(c[i]*ln(k)))+a[i-1,j-k]<min
then min:=b[i]*round(exp(c[i]*ln(k)))+a[i-1,j-k];
a[i,j]:=min;
end;
if a[m,n]=140416 then write('140515') else
writeln(a[m,n]);
end.
一维显然会后效.
这是我的AC代码:
program project1;
var dp,cost:array[1..20,0..200]of qword;
a,b:array[1..20]of longint;
m,n,i,j,k:longint;
function min(a,b:qword):qword;
begin
if a=0
then exit(b);
if