这个不算是dp，就是一个思维题，好难想的思维题，看了题解才写出来的，

把点和边分开，如果一条边的两个点颜色不同就是特殊边，特殊边两边连的点就叫特殊点，

如果一个点的被计算的次数等于特殊边的次数，则说明它是我们所求的点

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define inf 0x3f3f3f3fusing namespace std;typedef long long ll;const int maxn = 1e5 + 10;int num[maxn], a[maxn];pair
            
             pii[maxn];int main(){ int n; scanf("%d", &n); for(int i=1;i
            
           
          
         
        
       
      

这个我觉得挺难的。。。。

网上题解，dp[i]来表示激活第i个位置，从前面往后推到第i个位置，这个塔存留下来的数量。

这个是线性的，后面那个位置都是由前面的那个位置推过来的，如果我们选了后面那个位置，如果后面的无法把前面的那个位置炸掉

那么只能不炸，或者由最后添加的那个点来炸掉之前你需要炸掉的区间。

这个题目简单，是因为可以转化成线性的，不过我觉得好难想。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define inf 0x3ff3f3fusing namespace std;const int maxn = 1e6 + 10;int d[maxn], dp[maxn];int main(){ int n; scanf("%d", &n); int mm = 0; for(int i=1;i<=n;i++) { int a; scanf("%d", &a); scanf("%d", &d[a]); mm = max(mm, a); } if (d[0]) dp[0] = 1; int res = min(n, n - dp[0]); for(int i=1;i<=mm;i++) { if (d[i] == 0) dp[i] = dp[i - 1]; else { if (d[i] >= i) dp[i] = 1; else { dp[i] = dp[i - 1 - d[i]] + 1; } } res = min(res, n - dp[i]); } printf("%d\n", res); return 0;}