ToB企服应用市场:ToB评测及商务社交产业平台

标题: CF 1927 [打印本页]

---

作者: 傲渊山岳    时间: 2024-4-27 10:04
标题: CF 1927
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

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4