BZOJ1222[HNOI2001]제품가공[DP]

13048 단어 DPBZOJ

[H N O I 2001] 제품 가공 [HNOI 2001] 제품 가공 [HNOI 2001] 제품 가공


Description:
  • 모 가공 공장에 A, B 두 대의 기계가 있는데 가공된 제품은 그 중 어느 한 대의 기계가 완성하거나 두 대의 기계가 공동으로 완성할 수 있다.기계의 성능과 제품 특성의 제한을 받아 서로 다른 기계가 같은 제품을 가공하는 데 소요되는 시간이 다르기 때문에 만약 두 대의 기계가 공동으로 가공을 한다면 완성된 임무는 또 다르다.어느 날, 가공 공장에서 n개의 제품을 가공하는 임무를 받았는데, 매 임무의 작업량이 모두 같지 않았다.당신의 임무는 다음과 같습니다. 모든 임무가 A기계에서 가공하는 데 필요한 시간 t1, B기계에서 가공하는 데 필요한 시간 t2와 두 기계가 공동으로 가공하는 데 필요한 시간 t3을 알고 있습니다. 임무의 스케줄링 순서를 합리적으로 안배하여 모든 n개의 임무를 완성하는 총 시간을 최소화하세요.

  • Input Format:
  • 총 n+1줄 제1행위 n을 입력한다.n은 퀘스트 총수(1≤n≤6000) 제i+1행위 3개[0,5] 사이의 비음정수 t1, t2, t3으로 각각 i번째 퀘스트가 A기계에서 가공, B기계에서 가공, 두 기계가 공동으로 가공하는 데 필요한 시간을 나타낸다.만약 주어진 시간 t1 또는 t2가 0이면 임무가 이 기계에서 가공할 수 없다는 것을 의미하고, t3이 0이면 임무가 두 기계에서 동시에 가공할 수 없다는 것을 의미한다.

  • Output Format:
  • 최소 완료 시간
  • Sample Input:
  • 5 2 1 0 0 5 0 2 4 1 0 0 3 2 1 1

  • Sample Output:
  • 9

  • TJ:


    DP[i][tag]는 현재 기계 1이 i인 경우, 기계 2의 최소 사용 시, tag는 스크롤 그룹 표시를 나타냅니다.
    
    ```#include<bits/stdc++.h>
    using namespace std;
    auto ____ = [] () {ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); };
    const int MAXN = 3e5+7;
    const int INF = 0x3f3f3f3f;
    int n,f[MAXN][2],a[MAXN],b[MAXN],c[MAXN],m;
    int main(){
        ____();
        cin >> n;
        memset(f,INF,sizeof(f));
        for(int i = 1; i <= n; i++){
            cin >> a[i] >> b[i] >> c[i];
            m += max(a[i],c[i]);
        }
        int tag = 0;
        f[0][tag] = 0;
        for(int i = 1; i <= n; i++){
            tag^=1;
            for(int j = 0; j <= m; j++){
                f[j][tag] = INF;
                if(a[i]&&j>=a[i]) f[j][tag] = min(f[j][tag],f[j-a[i]][tag^1]);
                if(b[i]) f[j][tag] = min(f[j][tag],f[j][tag^1]+b[i]);
                if(c[i]&&j>=c[i]) f[j][tag] = min(f[j][tag],f[j-c[i]][tag^1]+c[i]);
            }
        }
        int ans = INF;
        for(int i = 0; i <= m; i++) ans = min(ans,max(i,f[i][tag]));
        cout << ans << endl;
        return 0;
    }
    

    좋은 웹페이지 즐겨찾기