2022SCUT Winter Training Day 7 记录（dp专题）

糖果 - 题库 - 计蒜客

二维dp，f [ i ][ j ] 表示选到第 i 个糖果，k的余数是 j 时，最大的选择糖果数。

特别注意初始化，要memset为-0x3f，而不是0

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 105;
int n, k, a[maxn], f[maxn][maxn];
int mo(int x) {return (x%k+k)%k;}
int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin>>n>>k; for(int i=1; i<=n; i++) cin>>a[i];
    memset(f,-0x3f,sizeof(f)); f[0][0] = 0;
    for(int i=1; i<=n; i++)
    for(int j=0; j 

H - 字符串折叠 
[SCOI2003]字符串折叠 - 洛谷
 
首先不难发现，折叠方式有很多种，并且可以套娃折叠，一个大区间中可能有多个小区间被折叠。所以想到区间dp。可以用f [ i ][ j ]表示 i 到 j 部分的字符串被压缩的最小长度。
 
#include 
using namespace std;
//f[i][j]表示i到j部分的字符串被压缩的最小长度
string s; int n, m[105], f[105][105];
void init(){
    //预处理数位长度
    for(int i=1; i<=9; i++) m[i]=1;
    for(int i=10; i<=99; i++) m[i]=2;
    m[100] = 3;
    //初始化折叠消耗
    memset(f,0x3f,sizeof(f));
    for(int i=1; i<=n; i++) f[i][i]=1;
}
bool check(int l, int r, int len){
    for(int i=l; i<=r; i++) //检查是否每个循环节都一样
        if(s[i] != s[(i-l)%len+l]) return false;
    return true;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin>>s; n=s.size(); s=' '+s; //处理一下让下标从1开始
    init();
    for(int l=2; l<=n; l++)
    for(int i=1,j=i+l-1; j<=n; i++,j++){
        for(int k=i; k 

F-纪念品  
[CSP-J 2019] 纪念品 - 题库 - 计蒜客
 
把当前价格看成weight，明天价格减今天价格看成value，跑 t 次完全背包。
 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 105;
int t, n, m, p[maxn][maxn], f[10005];
signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin>>t>>n>>m;
    for(int i=1; i<=t; i++)
    for(int j=1; j<=n; j++)
        cin>>p[i][j]; //第i天，第j个物品
    for(int k=1; k 

J - 互不侵犯King 
[SCOI2005]互不侵犯 - 洛谷
 
可以看做每个king会影响同行和下一行的相邻king。所以可以先预处理同行的可能情况（存到bit数组中），然后对每一行的情况进行状压dp。用 f [ i ][ j ][ k ]表示第 i 行，当前行情况为 j （二进制数位表示），总共放了 k 个king时，可能的情况数。
 
#include 
#include 
#include 
#include 
#include 
#define int long long
using namespace std;
int n, K, f[10][520][100], bit[520], cnt[520], size;
void dfs(int b,int c,int pos){ //预处理一行的情况
    if(pos>=n) {bit[++size]=b; cnt[size]=c; return;}
    dfs(b,c,pos+1); //这里不放king
    dfs(b+(1<>n>>K;
    dfs(0,0,0);
    for(int i=1; i<=size; i++) f[1][i][cnt[i]]=1; //第一行，所有状态都是一种情况
    for(int i=2; i<=n; i++) //枚举当前行数
    for(int j=1; j<=size; j++) //枚举当前行状态
    for(int k=1; k<=size; k++){ //枚举上一行状态
        if(bit[j] & bit[k]) continue;
        if((bit[j]<<1) & bit[k]) continue;
        if((bit[j]>>1) & bit[k]) continue;
        for(int c=cnt[j]; c<=K; c++) f[i][j][c] += f[i-1][k][c-cnt[j]];
    }
    int ans = 0;
    for(int i=1; i<=size; i++)
        ans += f[n][i][K];
    cout<
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5711736.html