开发笔记:acm选修课——动态规划

动态规划

概念

求最优&＃xff0c;
满足最优性原理&＃xff1a;
有最优子结构&＃xff0c;从小规模最优化到大规模最优化
又名&＃xff1a;记忆化搜索

对比

贪心&＃xff1a;从小到大
分治&＃xff1a;子问题求解独立

证明

求状态转移方程的过程
就是暴力剪枝&＃xff0c;记忆化搜索

例题

1.最长上升子序列

http://poj.org/problem?id&＃61;2533

找最长上升子序列
优化&＃xff1a;可以想到&＃xff0c;f[i]&＃xff0c;第i个上升子序列的最小值&＃xff0c;是持续递增的&＃xff08;反证法&＃xff09;&＃xff0c;以此改成了二分

#include
#include
#include
#ifdef LOCAL
FILE*fp&＃61;freopen("text.in","r",stdin);//文件忘记注释害人不浅&＃xff01;&＃xff01;
#endif
int a[1005],f[1005]; //第i个的最小值
signed main(){
int n;
scanf("%d",&n);
for(int i&＃61;0;i<n;i&＃43;&＃43;){
scanf("%d",&a[i]);
}
int cnt&＃61;0;
memset(f,0x3f,sizeof(int)*(n&＃43;1));
f[0]&＃61;-1;//注意边界数据。。
//可以想到&＃xff0c;是持续递增的&＃xff0c;可以以此二分
for(int i&＃61;0;i<n;i&＃43;&＃43;){
int l&＃61;0,r&＃61;cnt,m&＃61;(l&＃43;r)/2;//初始化
while(l<r){
if(f[m]<a[i]&&f[m&＃43;1]>&＃61;a[i])break;
if(f[m&＃43;1]<a[i])l&＃61;m&＃43;1;
if(f[m]>&＃61;a[i])r&＃61;m;
m&＃61;(l&＃43;r)/2;//注意顺序
}
f[m&＃43;1]&＃61;a[i];
if(m&＃61;&＃61;cnt)cnt&＃43;&＃43;;
/*for(int j&＃61;cnt;j>&＃61;0;j--){
if(f[j]&＃61;a[i]){
f[j&＃43;1]&＃61;a[i];
if(j&＃61;&＃61;cnt)cnt&＃43;&＃43;;
}
}*/
}
printf("%d\\n",cnt);
return 0;
}


2.数塔

http://acm.hdu.edu.cn/showproblem.php?pid&＃61;2084
自底向上

代码

#include
#include
#include
int a[1005],f[1005]; //第i个的最小值
signed main(){
int n;
freopen("text.in","r",stdin);
scanf("%d",&n);
for(int i&＃61;0;i<n;i&＃43;&＃43;){
scanf("%d",&a[i]);
}
int cnt&＃61;0;
memset(f,0x3f,sizeof(int)*(n&＃43;1));
f[0]&＃61;-1;//注意边界数据。。
for(int i&＃61;0;i<n;i&＃43;&＃43;){
for(int j&＃61;cnt;j>&＃61;0;j--){
if(f[j]<a[i]&&f[j&＃43;1]>a[i]){
f[j&＃43;1]&＃61;a[i];
if(j&＃61;&＃61;cnt)cnt&＃43;&＃43;;
}
}
}
printf("%d\\n",cnt);
return 0;
}


3.最长公共子序列

https://www.luogu.com.cn/problem/P1439

1.正常想法&＃xff1a;

#include
using namespace std;
#ifdef LOCAL
FILE*fp&＃61;freopen("text.in","r",stdin);
#endif
int a[100003],b[100003],s[2][100003];//滚动数组节省空间
int main(){
int t;
scanf("%d",&t);
for(int i&＃61;1;i<&＃61;t;i&＃43;&＃43;){
scanf("%d",&a[i]);
}
for(int i&＃61;1;i<&＃61;t;i&＃43;&＃43;){
scanf("%d",&b[i]);
}

for(int i&＃61;1;i<&＃61;t;i&＃43;&＃43;){
s[i%2][0]&＃61;0;
for(int j&＃61;1;j<&＃61;t;j&＃43;&＃43;){
if(a[i]&＃61;&＃61;b[j]){
s[i%2][j]&＃61;s[(i&＃43;1)%2][j-1]&＃43;1;
}else{
s[i%2][j]&＃61;max(s[i%2][j-1],s[(i&＃43;1)%2][j]);
}
}
}
printf("%d\\n",s[t%2][t]);
return 0;
}


2.这里数据量大&＃xff0c;利用不重复&＃xff0c;化二公共匹配为按另一个一个中顺序为优先级的一上升子序列为好

#include
#ifdef LOCAL
FILE*fp&＃61;freopen("text.in","r",stdin);//文件忘记注释害人不浅&＃xff01;&＃xff01;
#endif
using namespace std;
map<int,int>m;
int a[100005],f[100005];
signed main(){
int n,te;
scanf("%d",&n);
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){
scanf("%d",&te);
m[te]&＃61;i;
}
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){
scanf("%d",&te);
a[i]&＃61;m[te];
}
memset(f&＃43;1,0x3f,sizeof(int)*(n&＃43;1));
int cnt&＃61;0;
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){
int l&＃61;0,r&＃61;cnt,m&＃61;(l&＃43;r)/2;
while(l<r){
if(f[m]<a[i]&&f[m&＃43;1]>&＃61;a[i])break;
if(f[m&＃43;1]<a[i])l&＃61;m&＃43;1;
else r&＃61;m;
m&＃61;(l&＃43;r)/2;
}
f[m&＃43;1]&＃61;a[i];
if(m&＃61;&＃61;cnt)cnt&＃43;&＃43;;
}
printf("%d",cnt);
return 0;
}


4.字符串的修改

https://www.luogu.com.cn/problem/P2758

5.海盗分赃

http://acm.hdu.edu.cn/showproblem.php?pid&＃61;1538

6.The Uxuhul Voting System

http://acm.hnu.cn/online/?action&＃61;problem&type&＃61;show&id&＃61;10526&courseid&＃61;0

附加题&＃xff1a;

1.Doing Homework HDU - 1074【状压dp】

http://acm.hdu.edu.cn/showproblem.php?pid&＃61;1074

#include
#ifdef LOCAL
FILE*FP&＃61;freopen("text.in","r",stdin);
#endif
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
char str[15][102];
int d[15],c[15],s[1<<15],p[1<<15];
int Day(int now){
int sum&＃61;0,cnt&＃61;0;
while(now){
if(now&1)sum&＃43;&＃61;c[cnt];
now>>&＃61;1;
cnt&＃43;&＃43;;
}
return sum;
}
void print(int num){
if(num&＃61;&＃61;0)return;
print(num-(1<<p[num]));
printf("%s\\n",str[p[num]]);
}
signed main(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
for(int i&＃61;0;i<n;i&＃43;&＃43;){
scanf("%s%d%d",str[i],&d[i],&c[i]);
}
s[0]&＃61;0;
int num&＃61;(1<<n)-1;
for(int i&＃61;1;i<&＃61;num;i&＃43;&＃43;){
s[i]&＃61;INF;
int day&＃61;Day(i);
for(int j&＃61;0;j<n;j&＃43;&＃43;){
if(!((i>>j)&1))continue;//再次提醒&＃xff1a;&＃xff01;单目优先级高
int te&＃61;s[i-(1<<j)]&＃43;max(0LL,day-d[j]);
if(te<&＃61;s[i]){
s[i]&＃61;te;
p[i]&＃61;j;
}
}
}
printf("%lld\\n",s[num]);
print(num);
}
return 0;
}


2.hdu1024 max sum plus plus

http://acm.hdu.edu.cn/showproblem.php?pid&＃61;1024

#include
using namespace std;
#define N 1000005
#define INF 0x3f3f3f3f
int a[N],s[N],p[N];
int t,m,n,ma;
int main(){
while(~scanf("%d%d",&m,&n)){
for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){
scanf("%d",&a[i]);
}
memset(s,0,sizeof(int)*(n&＃43;2));
memset(p,0,sizeof(int)*(n&＃43;2));
for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){
//ma&＃61;-INF;
for(int j&＃61;i;j<&＃61;n;j&＃43;&＃43;){
s[j]&＃61;max(s[j-1],p[j-1])&＃43;a[j];
if(j&＃61;&＃61;i)p[j-1]&＃61;-INF,s[j-1]&＃61;-INF;
else p[j-1]&＃61;max(p[j-2],s[j-1]);
//p[j-1]&＃61;ma;//完成上行使命2333
//ma&＃61;max(ma,s[j]);//由于s[i-1]是可能更大的&＃xff0c;所以要-INF
}
}
printf("%d\\n",*max_element(s&＃43;m,s&＃43;n&＃43;1));
}
}