当前位置: 首页 > 工具软件 > Diablo > 使用案例 >

暗黑破坏神(diablo.pas/c/cpp)

鲜于高明
2023-12-01
                    **暗黑破坏神(diablo.pas/c/cpp)**

【问题描述】
游戏的主人公有n 个魔法,每个魔法分为若干个等级,第i 个魔法有p[i]个等级,每个
魔法的每个等级都有一个效果值,一个j 级的i 种魔法的效果值为w[i,j],魔法升一级需要一
本相应的魔法书,购买魔法书需要金币,第i 个魔法的魔法书价格为c[i],而小x 只有m 个
金币。
你的任务就是帮助小x 决定如何购买魔法书才能使所有魔法的效果值之和最大,开始的
时候所有魔法都是0 级,效果值为0。
【输入】
第一行用空格隔开的两个正整数n 和m,表示魔法的总数和金币的数量。
以下n 行,描述n 个魔法,第i+1 行描述第i 个魔法,均为整数。格式如下:
C[i] p[i] w[i,1] w[i,2] w[i,3]…w[i,p[i]]。
【输出】
输出只有一行一个整数,表示最大的魔法效果总和。
【输入输出样例1】
diablo.in
3 10
1 3 1 2 2
2 3 2 4 6
3 3 2 1 10

diablo.out
11
【样例说明】
样例中,第一个魔法升一级,需要1 个金币,得到效果值1,第二个魔法不升级,得到
效果值0,第三个魔法升到三级,需要9 个金币,得到效果值10,所以总的效果值是11。
注意,效果值不一定是正整数。
【数据范围】
0

#include<bits/stdc++.h>
using namespace std;
int n,m;
int v[101],c[101],p[101],w[101][51];
int f[101][51],d[101][51];
int main()
{
     freopen("diablo.in","r",stdin);
     freopen("diablo.out","w",stdout);
     scanf("%d%d",&n,&m); 
     for(int i=1;i<=n;i++)
     {
         scanf("%d%d",&c[i],&p[i]);
         for(int j=1;j<=p[i];j++)
           scanf("%d",&w[i][j]);
     }
     for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++) 
         for(int k=0;k<=p[i];k++) 
         {
             if(j<k*c[i]) break;
             else
             {
                 f[i][j]=max(f[i][j],f[i-1][j-k*c[i]]+w[i][k]);
                 d[i][j]=k;
             }
         }
    printf("%d",f[n][m]);
    return 0;
}

pascal的AC代码

var
  n,m,s,a1,x,i,j,k,max:longint;
  a,f1:array[0..500,0..500] of longint;
  w,t,f,c,f2:array[0..10000] of longint;
begin
  readln(n,m);
  for i:=1 to n do
    begin
      read(c[i],a[i,0]);
      for j:=1 to a[i,0] do
        begin
          read(x);
          inc(a1);
          w[a1]:=c[i]*j;
          t[a1]:=x;
          a[i,j]:=a1;
        end;
      readln;
    end;
  for k:=1 to n do
    for j:=m downto 0 do
      for i:=1 to a[k,0] do
        if j>=w[a[k,i]] then
          if f[j-w[a[k,i]]]+t[a[k,i]]>f[j] then
            begin
              f[j]:=f[j-w[a[k,i]]]+t[a[k,i]];
              f1[k,j]:=i;
            end;
  writeln(f[m]);
end.
 类似资料: