E.来硬的

E.来硬的

三眼dp

先说属性f[x][y]

x熔炼体积

y为1表示使用过了暗物质 y为0表示未使用

综合起来就是在使用（未使用）暗物质时，熔炼x单位体积矿石所用的时间

考虑到 燃料燃烧完之前，你不可以获取熔炉中的矿物。

当熔炼体积超过目标题解时更新目标体积的值

状态转移看代码

#include<vector>
#include<cstring>
using namespace std;
typedef long long int ll;
const int N=1e6+10,M=1e6+10;
ll n,m;
ll x[N],y[N];
ll f[M][2];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>x[i]>>y[i];
    }
    memset(f,0x3f,sizeof f);
    f[0][0]=0;
    for(ll i=1;i<=n;++i){
        for(ll j=m-1;j>=0;j--){//化简掉了第几个物品维度所以有大到小遍历
        	//不选用该煤炭 物品维度化简此操作省略 不懂建议再去看看背包问题
            
            //直接使用该煤炭 体积+x[i] 时间+y[i]
            f[min(j+x[i],m)][0]=min(f[min(j+x[i],m)][0],f[j][0]+y[i]);
            f[min(j+x[i],m)][1]=min(f[min(j+x[i],m)][1],f[j][1]+y[i]);
            
            //将该煤炭升级为暗物质后使用 体积+x[i]*2 时间+y[i]/2
            f[min(j+x[i]*2,m)][1]=min(f[min(j+x[i]*2,m)][1],f[j][0]+y[i]/2);
        }
    }
    cout<<min(f[m][0],f[m][1]);
    
}