题目描述
\,\,\,\,\,\,\,\,\,\,待榜之期，漫长如年。为自己和竹鼠们的生计，清楚在京师寻得一份张贴布告之差事，既可糊口，亦广交良朋，共商寻宝大业。
\,\,\,\,\,\,\,\,\,\,某日，清楚在张贴布告时，浆糊不慎落于羊皮卷上，湿透之处，竟现复杂图形……
\,\,\,\,\,\,\,\,\,\,清楚需要在长度为 nnn 个单位的布告板上张贴至多 nnn 张布告，第 iii 张布告的长度为 aia_iai 个单位，如果选择第 iii 张贴布告时需要满足：
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 第 iii 张布告必须要覆盖掉布告板的第 iii 个位置；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 布告不能够相互重叠，但是可以紧贴。
\,\,\,\,\,\,\,\,\,\,清楚想要知道自己按照要求，至少需要张贴几张布告，才能将布告板贴满。
输入描述:
\,\,\,\,\,\,\,\,\,\,每个测试文件均包含多组测试数据。第一行输入一个整数 T (1≤T≤100)T\ (1\le T\le 100)T (1≤T≤100) 代表数据组数，每组测试数据描述如下：
\,\,\,\,\,\,\,\,\,\,第一行输入一个整数 n (1≤n≤5000)n\ (1 \leq n \leq 5000)n (1≤n≤5000) 代表布告板的长度（同时也代表布告的张数）。
\,\,\,\,\,\,\,\,\,\,第二行输入 nnn 个整数 a1,a2,…,an (1≤ai≤n)a_1,a_2,\dots,a_n\ (1 \leq a_i \leq n)a1,a2,…,an (1≤ai≤n) 代表每一张布告的长度。
\,\,\,\,\,\,\,\,\,\,除此之外，保证所有的 nnn 之和不超过 500050005000 。
输出描述:
\,\,\,\,\,\,\,\,\,\,对于每一组测试数据，在一行上输出一个整数代表清楚至少需要贴的布告数量；如果无解，直接输出 −1-1−1 。
示例1
输入
复制2 4 1 2 2 3 3 2 2 2
2 4 1 2 2 3 3 2 2 2
输出
复制2 -1
2 -1
说明
\,\,\,\,\,\,\,\,\,\,对于第一组测试数据，有两种合法的选择方式：
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 贴第一、四张布告；
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,● 贴第二、三张布告；
\,\,\,\,\,\,\,\,\,\,对于第二组测试数据，无论怎么张贴都会有重叠部分。
做法
#include<bits/stdc++.h>
using namespace std;
int t,n;
int a[5010],dp[5010];//下标：布告板的第i个位置 值：布告板的张数
int main(){scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),dp[i]=0x3f3f3f3f;dp[0]=0;for(int i=1;i<=n;i++){//第i张布告板for(int j=0;j<=i-1;j++){//从布告板的第j个位置贴if(j+a[i]>=i&&j+a[i]<=n)//覆盖掉第i个位置，且在布告板范围内dp[j+a[i]]=min(dp[j+a[i]],dp[j]+1);}}if(dp[n]>5000) cout<<-1<<endl;else cout<<dp[n]<<endl;}
}wa的原因
没看清题目，没看到第 i 张布告必须要覆盖掉布告板的第 i 个位置；
