CF294B Shaass and Bookshelf [背包问题]

传送门

题目

操作和属性分析:

• 拥有n本书
• 第i本书的厚度是t[i] (输入的时候给的是n)
• 且这本书的纸张宽度是 w[i]
• 书的厚度是1或2
• 找一些书竖直放置
• 将剩余的书籍水平放置在书上
• 水平放置的书的宽度和不能多余竖直放置的书的总厚度

思路分析:

• 嗯.好这个数据范围还挺小,DP走起来
• 观察一下 不难发现 每本书的状态有两种 放和 不放 (好家伙来吧01背包)
• 观察一下谁是背包容量（限制条件）
• 不难发现 这里最大的长度是限制条件 v[i] 厚度就相当于体积
• 那么厚度就相当于价值呗
• 好假设完成 我们来走一遍

代码实现:

    cin>>n;
    int sum = 0 ;
    for(int i=1;i>v[i]>>w[i];
        sum+=v[i];
    }
   ///memset(f,0x3f,sizeof f);
    for(int i=1;i=0;i--)
    {
        if(sum - i>=f[i])
        {
            ans = sum - i;
            break;
        }
    }
    cout