ZOJ 3331-Process the Tasks (DP)

Description
There are two machines A and B. There are n tasks, namely task 1, task 2, ..., task n. You must assign each task to one machine to process it. There are some facts you must know and comply with:

You must assign each task to only one machine to process.

At any time, a machine can process at most one task.

Task i (0 < i < n) can be processed if and only if each task j (0 < j < i) has been processed or processing.

If a task is processing on one machine, it cannot be interrupted.

You want to do finish all the tasks as soon as possible.
 
Input
 
There are multiple test cases. The first line of the input is an integer T (0 < T < 1000) indicating the number of test cases. Then T test cases follow. Each test case starts with an integer n (0 < n < 100). The ith line of the nextn lines contains two integers tA, tB (0 < tA, tB < 100), giving the time to process the ith task by machine A and machine B.
 
Output
 
For each test case, output the earliest time when all the tasks have been processed.
 
제목:
두 개의 기계가 있는데 A와 B가 있습니다. 지금은 N개의 임무가 있습니다. 모든 임무는 A기계로 하면ai시간이 필요하고 B기계로 하면bi시간이 필요합니다. a,b,n<100
모든 임무는 그 전의 임무를 하고 있거나 이미 끝내야만 시작할 수 있고 기계마다 한 가지 임무를 동시에 할 수 있다.
 
처음에 n^3 dpTLE를 썼는데 1000개의 데이터가 있는 것을 발견하고 n^2 방법을 생각했다.
우리는 dp[k][j]로 상태 k, j의 총 시간을 나타낸다. k는 0이고 1은 A의 시간이 길고 B의 시간이 길며 j는 긴 시간과 짧은 시간의 차이를 나타낸다. 차이는 a, b보다 작기 때문에 복잡도 n^2이다.
A나 B 기기에서 임무를 완성하면 된다는 것을 고려하면 구체적인 코드는 다음과 같다.

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
int dp[105][2][105];
int a[2][105],n;
void up(int i,int k,int j,int v)
{
    dp[i][k][j]=min(dp[i][k][j],v);
}
int main()
{
    int T,i,j,k;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++) scanf("%d%d",&a[0][i],&a[1][i]);
        memset(dp,1,sizeof(dp));
        dp[0][0][0]=0;
        dp[0][1][0]=0;
        for(i=1;i<=n;i++)
        {
            for(k=0;k<2;k++)
            {
                for(j=0;j<=100;j++)
                {
                    if(dp[i-1][k][j]>10000) continue;
                    up(i,k,a[k][i],dp[i-1][k][j]+a[k][i]);
                    if(a[k^1][i]>j)
                        up(i,1^k,a[k^1][i]-j,dp[i-1][k][j]-j+a[k^1][i]);
                    else up(i,k,j-a[1^k][i],dp[i-1][k][j]);
                }
            }
        }
        int ans=100000;
        for(k=0;k<2;k++)
            for(j=0;j<=100;j++) if(dp[n][k][j]) ans=min(ans,dp[n][k][j]);
        cout<<ans<<endl;
    }
    return 0;
}