E

题意:给定一个字符串,然后把给定的字符串变为合法序列,即每两个1之间的距离严格等于k
题解:构建dp数组
dp[i][0/1]当前第i位填0还是填1的最小操作数

当前位置如果填0,所求值.即i-1位填0还是填1的最小加上这位是否为1

当前位置如果填1,所求值即从i-k全部填0,所需要的数量再加上i-k位填1的操作数,或者从0到i全部填0,两者取最小,再加上该位是否为0

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int dp[maxn][2];
int sum[maxn];
char s[maxn];
int main() {
    int t; cin >> t;
    int cnt = 0;
    while (t--) {
        int n, k;
        cin >> n >> k;
        cin >> (s + 1);
        for (int i = 1; i <= n; i++) {
            if (s[i] == '1')
                sum[i] = sum[i - 1] + 1;
            else
                sum[i] = sum[i - 1];
        }

        for (int i = 1; i <= n; i++) {
            int las = max(0, i - k);
            //当前位是0
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][0]) + (s[i] == '1');
            //当前位是1，可以考虑前面都为0，或者k个之前是1
            dp[i][1] = min(dp[las][1] + sum[i - 1] - sum[las], sum[i - 1]) + (s[i] == '0');
        }
        cout << min(dp[n][0], dp[n][1]) << endl;
    }
}

F

题意:给定一个n*m的矩阵,然后只能向下或向右移动,然后每次移动的位置必须满足两者相差1,即3->4为成立,3->5不成立,现在可以对于每一个数可以进行任意次的-1操作,变成负数也行,然后来求从(1,1)到(n,m)最小操作数
题解:选定一个基点,然后枚举来求,如果操作数最小,那么最好是保证一个数不变才能求得最小操作数
然后对于每一个基点,来求从(1,1)到(n,m)得最小操作数,具体看代码

#include<bits/stdc++.h>
#define dbg(x) cout<<#x<<" = "<<x<<endl;
#define INF 0x3f3f3f3f
#define eps 1e-6

using namespace std;
typedef long long LL;   
typedef pair<int, int> P;
const int maxn = 120;
const int mod = 1000000007;
const LL llinf = 1e18;
LL a[maxn][maxn], dp[maxn][maxn];

int main()
{
    int t, n, m, i, j, k;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d", &n, &m);
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
                scanf("%I64d", &a[i][j]);
        LL ans = llinf;
        for(int a1=0;a1<n;a1++)
            for(int a2=0;a2<m;a2++)
        if(a[0][0] >= a[a1][a2]-a1-a2)
        {
            LL ps = a[a1][a2]-a1-a2;
            dp[0][0] = a[0][0]-ps;
            for(j=1;j<n;j++)
                if(a[j][0]<ps+j || dp[j-1][0] == llinf)dp[j][0] = llinf;
                else dp[j][0] = min(llinf, dp[j-1][0] + a[j][0]-ps-j);
            for(j=1;j<m;j++)
                if(a[0][j]<ps+j || dp[0][j-1] == llinf)dp[0][j] = llinf;
                else dp[0][j] = min(llinf, dp[0][j-1] + a[0][j]-ps-j);
            for(j=1;j<n;j++)
                for(k=1;k<m;k++)
                {
                    dp[j][k] = llinf;
                    if(a[j][k]<ps+j+k)continue;
                    dp[j][k] = min(dp[j][k], dp[j-1][k]+a[j][k]-ps-j-k);
                    dp[j][k] = min(dp[j][k], dp[j][k-1]+a[j][k]-ps-j-k);
                }
            ans = min(ans, dp[n-1][m-1]);
        }
        printf("%I64d\n", ans);
    }
    return 0;
}