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;
}
