动态规划训练

动态规划这玩意在ACM中比较重要，但个人对其理解不深，所以想刷刷相关题目，就在此记录下所刷题目（点击标题可进入原题地址）

1、被3整除的子序列

描述

给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除，答案对1e9+7取模

思路

对于一个整数，如果其所有位数之和是3的倍数，那么这个整数也就是3的倍数，证明很容易，这里略过。
那么，假设dp[i][j]表示前i个数字中的子序列，对3取余为j的数量，则dp[i+1][j]就可由前面和第i+1个数字推出。
举个例子，第i+1个数字取余3为2，那么
dp[i+1][0] += dp[i][1] //前面i个子序列中，余数为1的组合，加上余数为2便是余数为0了
dp[i+1][1] += dp[i][2] //前面i个子序列中，余数为2的组合，加上余数为2便是余数为1了
dp[i+1][2] += dp[i][0]+ 1 //前面i个子序列中，余数为0的组合，加上余数为2便是余数为2，同时还得加上第i+1个数字本身
其他情况同理，此外，由于每次只需用到前面i个子序列的情况，而1--i-1不需用到，所有dp还可优化到一维。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9+7;
int dp[5];
int main(){
    char x[55];
    while(cin >> x){
        memset(dp,0,sizeof(dp));
        int len = strlen(x);
        for(int i = 0;i < len;i++)
            x[i]-='0';
        dp[x[0]%3] = 1;
        for(int i = 1;i < len;i++){
            if(x[i]%3 == 0){
                dp[0] = (dp[0]<<1)+1;
                dp[1]<<=1;
                dp[2]<<=1;
            }
            else if(x[i]%3 == 1){
                int temp0 = dp[0],tmep1 = dp[1];
                dp[0]+=dp[2];
                dp[1]+=temp0+1;
                dp[2]+=tmep1;
            }
            else{
                int temp0 = dp[0];
                dp[0]+=dp[1];
                dp[1]+=dp[2];
                dp[2]+=temp0+1;
            }
            for(int i = 0;i < 3;i++)
                dp[i]%=mod;
        }
        cout << dp[0] << endl;
    }
    return 0;
}

2、牛牛的计算机内存

描述

牛牛的计算机一共有m块内存，现在有n条指令，每条指令是一个01序列
如果指令的第i个字符为1，说明这条指令需要访问第i块内存
每条指令的执行代价为k^2, k为新访问内存的数量，即之前的指令都没有访问到的内存数量
你可以随意安排n条指令的执行顺序，求执行完所有指令的最小代价
（n,m <= 20）

思路

n条指令，可以用二进制代表其是否已执行，如1001表示第1和第4条指令已执行，第2和第3条指令未执行
那么，状态转移，从结果回推到开始，举个例子
此时n=4，假设要执行完所有4条指令指令，即令二进制为1111
那么，其前面情况必然是0111，1011，1101，1110这四种情况之一，取他们加上执行未执行指令的代价，取最小即可
而这些可通过[0,1<<n)一重循环表示情况，接下来[1,n]是第二重循环表示选择指令解决。
部分题解弄了个滚动数组，又多加了[1,n]循环，即三重循环，其实完全没必要。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 0x3f3f3f3f;
char a[25][25];
int b[25],dp[1<<20],val[1<<20];
int to_ten(char x[]){
    int ans = 0;
    for(int i = strlen(x)-1,j = 1;i >= 0;i--,j<<=1)
        ans+=(x[i] == '1')?j:0;
    return ans;
}
int get_value(int x,int y){
    int ans = 0;
    for(int i = 0;i < 21;i++)
        if((x&(1<<i)) && !(y&(1<<i))) ans++;
    return ans*ans;
}
int main(){
    int n,m;
    cin >> n >> m;
    memset(dp,0x3f,sizeof(dp));
    dp[0] = 0;
    for(int i = 0;i < n;i++){
        cin >> a[i];
        b[i] = to_ten(a[i]);
    }      
    for(int j = 0;j < (1<<n);j++){
        if(dp[j] == inf) continue;
        for(int u = 0;u < n;u++){
            if(!(j&(1<<u))){
                int temp = dp[j]+get_value(b[u],val[j]);
                if(temp < dp[j|(1<<u)]){
                    dp[j|(1<<u)] = temp;
                    val[j|(1<<u)] = b[u]|val[j];
                }
            }
        }
    }
    cout << dp[(1<<n)-1] << endl;
    return 0;
}