当前位置：首页 > news >正文

打卡信奥刷题（2957）用C++实现信奥题 P5924 [IOI 2004] Phidias 菲迪亚斯神

news 2026/5/12 8:03:56

P5924 [IOI 2004] Phidias 菲迪亚斯神

题目背景

有名的希腊雕刻神菲迪亚斯正在为他下一座雄伟的雕像作准备。

题目描述

为了这座雕像他需要大小为W1×H1,W2×H2,...,WN×HNW_1\times H_1,W_2\times H_2, ...,W_N \times H_NW1×H1,W2×H2,...,WN×HN的矩形大理石板。

最近菲迪亚斯获得一块矩形大理石块。菲迪亚斯想把这块石板切成所需要的大小。

石板或是石板所切割出的部分都可以由垂直(或水平)方向纵贯(或是横贯)加以切割到底成为两块矩形石板，同时切割出的这两块矩形石板都必须具有整数的宽度与高度。

石板只能以此种方法加以切割，同时石板不能粘合成较大石板。

因为石板具有花纹，所以石板也不能旋转。

如果菲迪亚斯切割出一块A×BA\times BA×B的石板，则此石板不能被当成B×AB\times AB×A的石板使用，除非AAA等于BBB。对每一种所需石板大小菲迪亚斯可切割出零或更多块石板。如果当所有的切割完成时，一块产生出的石板并不是任何所需要的大小，则此石板成为废料。

菲迪亚斯想知道如何切割最初的石板，才能让所产生的废料最少。

例如，下图中的原始石板宽度为212121且高度为111111，而所需石板大小为10×4,6×2,7×510\times4,6\times 2, 7\times510×4,6×2,7×5及15×1015\times 1015×10, 则最小废料总面积为101010。下图同时画出最小废料总面积为101010的切割方法：

你的工作是写一个程序由给定的原始石板大小及所需要的各种石板大小计算出最小的废料总面积。

输入格式

第一行为两个整数。

第一个整数WWW为原始石板的宽度，第二个整数HHH为原始石板的高度。

第二行为一个整数NNN，代表所需石板种类数目。以下NNN行为各种所需石板的大小。

每一行为两个整数，第一个整数为所需石板宽度WiW_iWi，第二个整数为所需石板宽度HiH_iHi。

输出格式

为一行且仅包含一个整数，代表最小废料总面积。

输入输出样例 #1

输入 #1

21 11 4 10 4 6 2 7 5 15 10

输出 #1

说明/提示

对于100%100\%100%的数据，1≤W,H≤6001\le W,H\le6001≤W,H≤600，0≤N≤2000\le N\le 2000≤N≤200，1≤Wi≤W1 \le W_i \le W1≤Wi≤W，1≤Hi≤H1 \le H_i \le H1≤Hi≤H。

C++实现

#include<bits/stdc++.h>#definerep(i,a,b)for(inti=(a),stOwxc=(b);i<=stOwxc;i++)#defineper(i,a,b)for(inti=(a),stOwxc=(b);i>=stOwxc;i--)usingnamespacestd;typedeflonglongll;constintN=1000+5;intW,H,n;intF[N][N];inta[N],b[N];intdfs(intw,inth){int&f=F[w][h];if(f!=-1)returnf;f=w*h;rep(i,1,n)if(a[i]<=w&&b[i]<=h)f=min({f,dfs(w-a[i],b[i])+dfs(w,h-b[i]),dfs(a[i],h-b[i])+dfs(w-a[i],h)});returnf;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>W>>H;cin>>n;rep(i,1,n)cin>>a[i]>>b[i];memset(F,-1,sizeof(F));cout<<dfs(W,H)<<'\n';return0;}