1、DP，f表示合并区间内的珠子获得最大能源
2、DP，可以先把主件和附件的搭配全部分出来，然后分阶段做背包
3、模拟
4、递推+高精度
1．
这题具有最优子结构的性质，与合并石子相似，所以可以用动态规划来做。首先将数据存于c数组中，每次需要枚举一下起始点i和终点j的位置，还要枚举起点和终点之间一个断点k的位置，表示第i—k个珠子已经合并在了一起，第k—j个珠子也已经合并在了一起，当前要合并的是这两个已经合并在了一起的小珠子，这样就把一个问题分成了许多子问题。当前一次操作所产生的能量K=c[i]*c[k]*c[j]
具体做法是：开一个二维数组a，a[i,j]表示从i开始到j结束这一段中所有珠子合并所能产生的能量的最大值。然后先枚举段的长度i（i为2到N），接着枚举开始位置j，由i, j可推出结束位置k。然后枚举断点位置v，v为j+1到k-1之间。在每个断点处断开所能获得的能量为K=c[j]*c[v]
*c[k]+a[j,v]+a[v,k]。取这中间的一个最大值赋给a[j , k]。这样做的时间复杂度为O(n3)，因为N<=100，所以时间上肯定没有问题。最后a[i,i]的最大值就是合并所有珠子后所能产生的能量的最大值。
const
maxn=100;
var
c:axn] of longint;
a:axn] of longint;
n,i,j,k,t,v,u,max:longint;
begin
assign(input,'energy.in'); ret(input);
lunch是什么意思
assign(output,'energy.out'); rewrite(output);
readln(n);
for i:=0 to n-1 do read(c[i]);
fillchar(a,sizeof(a),0);
for i:=2 to n do begin
for j:=0 to n-1 do begin
k:=(j+i) mod n;
max:=0;
for v:=j+1 to j+i-1 do begin
u:=v mod n;
t:=c[j]*c[u]*c[k]+a[j,u]+a[u,k];
if t>max then max:=t;
南京营养师培训 end;
a[j,k]:=max;
end;
end;
max:=0;
for i:=0 to n-1 do
if a[i,i]>max then max:=a[i,i];
writeln(max);
clo(input); clo(output)
end.
2、
此题初看MS是01背包问题，只是多了附件这个条件。注意到每个主件最多只有2个附件和附件不再带有附件，我们就可以把附件和主件合并起来解决。每个主件最多有4种状态，即：只用主件，用主件+1号附件，1主件+2号附件和1主件+2个附件。先通过搜索得出每个状态。问题得以解决。
const
maxm=60;
maxn=32000;
inf='budget.in';
outf='budget.out';
var
v,w,d,q:axm]of integer;
a,b:axn,0..4]of longint;
f:array[0..axn]of longint;
n,m,tot:integer;
ans:longint;
procedure init;
var
i:integer;
begin
fillchar(d,sizeof(d),0);
readln(n,m);
for i:=1 to m do begin
readln(v[i],w[i],q[i]);
v[i]:=v[i] div 10;
inc(d[q[i]]);
end;
end;
procedure tup;
var
i,j,k:integer;
begin
tot:=0;
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
for i:=1 to m do
if q[i]=0 then begin
if d[i]=0 then begin
inc(tot);
a[tot,0]:=1;
a[tot,1]:=v[i];
b[tot,1]:=v[i]*w[i];
end
el if d[i]=1 then begin
for j:=1 to m do if q[j]=i then break;
inc(tot);
a[tot,0]:=2;
a[tot,1]:=v[i];
a[tot,2]:=v[i]+v[j];
b[tot,1]:=v[i]*w[i];
b[tot,2]:=v[i]*w[i]+v[j]*w[j];
end
el begin
inc(tot);
身份证翻译 for j:=1 to m do if q[j]=i then break;
for k:=1 to m do if (q[k]=i)and(k<>j) then break;
a[tot,0]:=4;
a[tot,1]:=v[i];
a[tot,2]:=v[i]+v[j];
a[tot,3]:=v[i]+v[k];
a[tot,4]:=v[i]+v[j]+v[k];
b[tot,1]:=v[i]*w[i];
b[tot,2]:=v[j]*w[j]+v[i]*w[i];
b[tot,3]:=v[i]*w[i]+v[k]*w[k];
b[tot,4]:=v[i]*w[i]+v[j]*w[j]+v[k]*w[k];
end;
end;
end;
function max(x,y:longint):longint;
begin
if x>y then max:=x
el max:=y;
end;
英语小谜语procedure solve;
var
ans:longint;
i,j,k,nn,p:longint;
begin
英语六级准考证号 tup;
nn:=trunc(n/10);
fillchar(f,sizeof(f),0);
p:=1;
for i:=1 to tot do begin
f[p]:=f[1-p];
for j:=1 to a[i,0] do
for k:=a[i,j] to nn do
f[p,k]:=max(f[p,k],f[1-p,k-a[i,j]]+b[i,j]);
p:=1-p;
end;
ans:=0;
for i:=1 to n do if f[1-p,i]>ans then ans:=f[1-p,i];
爱情狂奔 writeln(ans*10);
end;
begin
assign(input,inf);
ret(input);
assign(output,outf);
rewrite(output);
init;
solve;
clo(input);
clo(output);
end.
3、
const
maxn = 20;
maxm = 20;
maxs = 5000;
type
Tq = record
st, ed:longint;
end;
var
n, m, i, j, k, ans:longint;
ma, tim, x, y:longint;
t:axn] of longint;
data, a:axn*maxm] of longint;
num:axm] of longint;
time:axm] of longint;
free:axs] of Tq;
count:axm] of longint;
last:axn] of longint;
function max(a, b:longint):longint;
begin
if a > b then max:=a el max:=b;
end;
function find_free(k, ma, tim:longint; var x, y:longint):longint;
var
i, minx, best:longint;
begin
minx:=maxlongint;
for i:=1 to count[ma] do
if free[ma, i].ed - free[ma, i].st >= tim then
if last[k] <= free[ma, i].st then
begin
christmas card if free[ma, i].st < minx then
begin
minx:=free[ma, i].st;
best:=i;
end;
end el
if (last[k] > free[ma, i].st) and (last[k] + tim <= free[ma, i].ed) then
begin
if last[k] < minx then
begin
minx:=last[k];
best:=i;
end;
end;
find_free:=best;
x:=minx;
y:=x + tim;
end;
begin
assign(input,'jsp.in');
ret(input);
assign(output,'jsp.out');
rewrite(output);
{ input }
read(m, n);
for i:=1 to m * n do read(data[i]);
for i:=1 to n do
for j:=1 to m do read(num[i, j]);
for i:=1 to n do
for j:=1 to m do read(time[i, j]);
{ Main }
fillchar(t, sizeof(t), 0);
for i:=1 to n * m do
begin
inc(t[data[i]]);
a[i]:=t[data[i]];
end;本科毕业证查询
fillchar(last, sizeof(last), 0);
for i:=1 to m do
begin
count[i]:=1;
free[i, 1].st:=0;
free[i, 1].ed:=maxlongint;
end;
for i:=1 to n * m do
begin
ma:=num[data[i], a[i]];
tim:=time[data[i], a[i]];
k:=find_free(data[i], ma, tim, x, y);
inc(count[ma]);
free[ma, count[ma]].st:=y;
free[ma, count[ma]].ed:=free[ma, k].ed;
free[ma, k].ed:=x;
杭州服装学校 last[data[i]]:=y;
end;
airasia com { output }
ans:=-1;
for i:=1 to m do
for j:=1 to count[i] do
if free[i, j].ed = maxlongint then
ans:=max(ans, free[i, j].st);
writeln(ans);
clo(input);
clo(output);
end.
