清楚姐姐的布告规划
时间限制：1秒 空间限制：512M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！ 
题目描述
待榜之期，漫长如年。为自己和竹鼠们的生计，清楚在京师寻得一份张贴布告之差事，既可糊口，亦广交良朋，共商寻宝大业。
某日，清楚在张贴布告时，浆糊不慎落于羊皮卷上，湿透之处，竟现复杂图形……
清楚需要在长度为
n
n
n 个单位的布告板上张贴至多
n
n
n 张布告，第
i
i
i 张布告的长度为
a
i
a_i
ai 个单位，如果选择第
i
i
i 张贴布告时需要满足：
● 第
i
i
i 张布告必须要覆盖掉布告板的第
i
i
i 个位置；
● 布告不能够相互重叠，但是可以紧贴。
清楚想要知道自己按照要求，至少需要张贴几张布告，才能将布告板贴满。
输入描述：
每个测试文件均包含多组测试数据。第一行输入一个整数
T
(
1
≤
T
≤
100
)
T (1≤T≤100)
T(1≤T≤100) 代表数据组数，每组测试数据描述如下：
-
第一行输入一个整数
n
(
1
≤
n
≤
5000
)
n (1≤n≤5000)
n(1≤n≤5000) 代表布告板的长度（同时也代表布告的张数）。
-
第二行输入
n
n
n 个整数
a
1
,
a
2
,
…
,
a
n
(
1
≤
a
i
≤
n
)
a_1,a_2,…,a_n (1≤a_i≤n)
a1,a2,…,an(1≤ai≤n) 代表每一张布告的长度。 除此之外，保证所有的
n
n
n 之和不超过
5000
5000
5000 。
输出描述：
对于每一组测试数据，在一行上输出一个整数代表清楚至少需要贴的布告数量；如果无解，直接输出
−
1
−1
−1 。
示例1
输入：
2
4
1 2 2 3
3
2 2 2
输出：
2
-1
说明：
对于第一组测试数据，有两种合法的选择方式：
● 贴第一、四张布告；
● 贴第二、三张布告；
对于第二组测试数据，无论怎么张贴都会有重叠部分。
解题思路
本题可转化为带约束的区间覆盖最小化问题，采用动态规划求解。每张布告对应长度固定的区间，放置时必须包含自身序号位置，且区间不可重叠，目标是用最少布告覆盖长度为n的整块布告板。 定义状态 dp[i] 表示覆盖前 i 个单位长度所需的最少布告数，初始 dp[0]=0，其余设为无穷大。对于每个右端点 i，枚举所有布告：若该布告可以 i 为右端点放置（区间包含自身序号且左端点不越界），则通过 dp[i – a[j]] + 1 更新 dp[i] 的最小值，其中 i – a[j] 为该布告左端点的前一位置。最终若 dp[n] 仍为无穷大则无解，否则即为答案。算法时间复杂度
O
(
n
2
)
O(n^2)
O(n2)，完全适配题目数据范围。
总结
核心逻辑：将布告的放置约束转化为区间右端点的合法性判断，通过动态规划递推得到覆盖每个长度的最小布告数。 关键操作：定义一维DP状态、枚举右端点与布告完成状态转移、边界越界校验、无穷大初始值处理。 效率保障：平方级复杂度匹配题目n≤5000的约束，总运算量可控，实现简洁直观。
代码简要说明
代码内容
#include <bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;
using ui=unsigned int;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;
void solve()
{
ll n;
cin>>n;
vector<ll> a(n,0),dp(n+1,INF);
for(ll i=0;i<n;i++) cin>>a[i];
dp[0]=0;
for(ll i=1;i<=n;i++)
{
for(ll j=0;j<i;j++)
{
if(i–j<=a[j]&&i–a[j]>=0)
{
dp[i]=min(dp[i],dp[i–a[j]]+1);
}
}
}
if(dp[n]==INF) cout<<–1<<"\\n";
else cout<<dp[n]<<"\\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
ll t=1;
cin>>t;
while(t—) solve();
return 0;
}
