luogu P1800 software_NOI导刊2010提高（06）(二分优化)

· · 题解

萌新第一次写题解，望包含

题面传送门

这道题很有难度

先观察题目:不难想到是一个背包题，背包容量:m,物品重量:1,物品数量:n

物品价值是什么?

是前i个人完成软件1后,最多能完成几个软件2

这便将问题转化为完全背包了

但是,如果纯打完全背包,只能得60分

怎么优化呢?

经过观察发现:答案具有单调性

于是可以用二分答案优化了

你懂了吗?可以看代码

/*
  This code is made by ghy.
  Algorithm : Two Points Answer && Dynamic Programming (DP).
  I don't know what this code is.
*/
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n,m,a[105],b[105],dp[105][105],l=1,r=20000;//r(max)=m(max)*day(max)=20000
bool check(int ntime){
    int time_else;
    memset(dp,0,sizeof(dp));    //记得初始化
    dp[0][0]=1;
    for(int i=1;i<=n;i++)   //枚举第i个人 
        for(int j=0;j<=m;j++)
            for(int k=j;k>=0;k--){
                time_else=ntime-a[i]*(j-k);    //表示前i个人模块1做了j-k个情况下,他们能用来做模块2的时间
                if(time_else<0)     //用ntime的时间做不了j-k个模块1       
                    break;
                if(dp[i-1][k]>0)    //前i-1个人可以做k个模块1的同时做1个及以上的模块2
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+time_else/b[i]);    //状态转移方程(类完全背包) 
            }
    return dp[n][m]>m;    //dp[n][m]:前n个人做m个模块1的同时,在time_else内还能做多少个模块2 
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i],&b[i]);
    int mid;
    while(l<=r){    //二分答案,其中l,r都能取到     
        mid=(r+l)>>1;
        if(check(mid))
            r=mid-1;
        else
            l=mid+1;
    }
    printf("%d\n",l);
    return 0;
}