Codeforces Round #178 (Div. 2) B Shaass and Bookshelf

B. Shaass and Bookshelf
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Shaass has n books. He wants to make a bookshelf for all his books. He wants the bookshelf's dimensions to be as small as possible. The thickness of the i-th book is ti and its pages' width is equal to wi. The thickness of each book is either 1 or 2. All books have the same page heights.

$\$

Shaass puts the books on the bookshelf in the following way. First he selects some of the books and put them vertically. Then he puts the rest of the books horizontally above the vertical books. The sum of the widths of the horizontal books must be no more than the total thickness of the vertical books. A sample arrangement of the books is depicted in the figure.

$\$

Help Shaass to find the minimum total thickness of the vertical books that we can achieve.

Input
The first line of the input contains an integer n, (1 ≤ n ≤ 100). Each of the next n lines contains two integers ti and wi denoting the thickness and width of the i-th book correspondingly, (1 ≤ ti ≤ 2, 1 ≤ wi ≤ 100).

Output
On the only line of the output print the minimum total thickness of the vertical books that we can achieve.

Sample test(s)
input
5
1 12
1 3
2 15
2 5
2 1
output
5
input
3
1 10
2 1
2 4
output
3

很久都没有写过关于ACM的东西了，退役也已经超过了一年多了。
在我以前做ACM的时候，codeforces还没有现在这么火爆，那时候我们都是去刷topcoder。
这次codeforces是突然心血来潮，想到反正没有别的事情，就做做

这个题是div2的B题，我先开始的想法是贪心，但是想了半天都没有处理好几种特殊的情况，后来就开始思考关于DP的方向。
由于以前学ACM的时候DP就一直很弱，所以搞了半天也没有推清楚状态的转移方程
最后没有办法，就只有使用唯一的那个选择：记忆化搜索

是的，如果这个题使用暴力搜索的话，其实还是很好写的。只需要去枚举每一本书是放在下面，或者是放在上面两种情况
当然如果不用记忆化，直接递归的话，在第九组数据的时候会TLE。

我的code：
[cpp]
#include<stdio.h>
#include<string.h>

int w[105],t[105],n;
int mem[105][205][205];

int min(int a,int b)
{
    if(a>b)
        return b;
    else
        return a;
}

int dfs(int pos,int thi,int whi)
{
    if(pos==n)
        return thi;
    if(mem[pos][thi][whi]!=-1)
        return mem[pos][thi][whi];
    if(thi-t[pos]>=whi+w[pos])
        return mem[pos][thi][whi]=min(dfs(pos+1,thi-t[pos],whi+w[pos]),dfs(pos+1,thi,whi));
    return mem[pos][thi][whi]=dfs(pos+1,thi,whi);
}

int main()
{
    int i,sum;
    while(scanf("%d",&n)!=EOF)
    {
        memset(mem,-1,sizeof(mem));
        sum=0;
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&t[i],&w[i]);
            sum=sum+t[i];
        }
        printf("%d\n",dfs(0,sum,0));
    }
    return 0;
}

补充：软件开发 , C++ ,