洛谷-P1504

latex有点问题，待修复！

~~这是我第一篇题解~~~

这道题可以用$DP$（动态规划）来做~

DP必备三步：

• $状态表示$
• $动态转移$
• $初始状态$

开始吧！$~~~~~$我们可以先只考虑单独城堡 $k$ ~~

---

$First~~状态表示$

• $dp[i][j]$ 表示用前 $i$ 块积木能否达到高度 $j$

---

$Next ~~动态转移$

• 不选第 $i$ 块积木 $dp[i][j] = dp[i-1][j]$

• 选第 $i$ 块积木 $dp[i][j] = dp[i-1][j-w[i]]$

倒叙降维,用 $|=$ 连接,得：

• $dp[j] ~~|= ~~dp[j-w[i]]$

---

$Last ~~初始状态$

很简单~

不搭积木肯定行呀！

• $dp[0] = 1$

---

用代码呈现~

#include <bits/stdc++.h> //万能头
using namespace std;

int n,len,min_high = 2e9,w[105],ans[10005];
// w数组为每一城堡积木的高度 ans数组为达到高度i的个数
bool dp[10005];
// Dp嘛
int main() {
    cin >> n; //n个城堡
    for(int k=1;k<=n;k++)// 每一个城堡
    {
        //memset(w,0,sizeof(w)); // 其实不用
        memset(dp,0,sizeof(dp)); // 以免前一个影响当前城堡
        int cnt = 0,high = 0; //cnt为积木个数，high为高度~
        while(1)
        {
            cin >> len; //输入len
            if(len == -1) break; // 输入完了~
            w[++cnt] = len; // 存高度~
            high += len; // 算高度~
        }
        // 开始DP！
        dp[0] = 1; // 初始状态
        for(int i=1;i<=cnt;i++)// 物品维（cnt个积木）
            for(int j=high;j>=w[i];j--)// 容量~倒叙枚举压物品维 枚举到物品大小
                dp[j] |= dp[j-w[i]]; //动态转移方程
        min_high = min(min_high,high); // 最小值~
        for(int i = high;i>=1;i--) // 检查一下能否达到高度
            if(dp[i] == 1) ans[i]++;// 加到ans数组~
    }
    for(int i = min_high;i>=1;i--)// 看看那个高度可以所有达到！
        if(ans[i] == n)
        {
            cout << i;// 输出
            return 0;
        }
    cout << "0";//没有，输出0
    return 0;
}

PS:代码两重循环，看范围，不会$TLE$的~