动态规划训练
动态规划这玩意在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;
}