G
题面
定义\({{dp_i}_j}_k\)为考虑完第i个点，最左边没有染色的点为\(j\)，最右边没有染色的点为\(k\)的最小数量。
考虑转移（用自己更新别人）
如果不用\(i\)，直接转移到\({{dp_{i+1}}_j}_k\)。
如果向左喷，\(k\)为\(max({i+1,k})\)，判断能喷到的位置
- 比\(j\)更靠左，\(j\)将变成\(max({i+2,k+1})\)（\(i+1\)的下一个或\(k\)的下一个将为最左边没有染色的）；
- 否则，\(j\)将不变。
如果向右喷，\(k\)为\(max({i+a_i-1,k})\)，判断能喷到的位置
- 比\(j\)更靠左，\(j\)将变成\(max({i+a_i,k+1})\)（\(i+a_i-1\)的下一个或\(k\)的下一个将为最左边没有染色的）；
- 否则，\(j\)将不变。
点击查看代码[code]#include#define int long longusing namespace std;int t;int n;int a[105];int q[105];int h[105];int dp[105][105][105];void mx(int &a,int b){ a = min(a,b);}void qwq(){ cin >> n; for(int i = 1;i > a; q = max(1ll,i-a+1); h = min(n,i+a-1); } memset(dp,0x3f,sizeof(dp)); dp[0][1][0] = 0; for(int i = 0;i < n;++ i){ for(int j = 1;j |
