0x5E「动态规划」练习
5E01 乌龟棋
考虑如何表示当前状态,d[x,i,j,k,l]表示目前在x位置,四种牌的使用张数分别为i,j,k,l时的最大分数。发现时间空间复杂度过高,因此考虑优化。
仔细观察后发现,只要知道四种牌的使用张数就能够算出当前位置x=i+2j+3k+4*l+1。因此修改状态定义如下:
状态表示:d[i,j,k,l]表示四种牌的使用张数分别为i,j,k,l时的最大分数
转移方程:
其他牌同理
边界:
目标:
时间复杂度:
代码如下:(ps:为了简化代码,使用了引用表示d[i,j,k,l])
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=350+5;
const int maxm=40+5;
const int INF=0x3f3f3f3f;
int d[maxm][maxm][maxm][maxm]={0},cnt1=0,cnt2=0,cnt3=0,cnt4=0,n,m,a[maxn],x;
int main() {
ios::sync_with_stdio(false);
//freopen("乌龟棋.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++){
cin>>x;
if(x==1) cnt1++;
if(x==2) cnt2++;
if(x==3) cnt3++;
if(x==4) cnt4++;
}
d[0][0][0][0]=a[1];
for(int i=0;i<=cnt1;i++){
for(int j=0;j<=cnt2;j++){
for(int k=0;k<=cnt3;k++){
for(int l=0;l<=cnt4;l++){
int &temp=d[i][j][k][l];
int v=a[i+2*j+3*k+4*l+1];
if(i) temp=max(temp,d[i-1][j][k][l]+v);
if(j) temp=max(temp,d[i][j-1][k][l]+v);
if(k) temp=max(temp,d[i][j][k-1][l]+v);
if(l) temp=max(temp,d[i][j][k][l-1]+v);
}
}
}
}
cout<<d[cnt1][cnt2][cnt3][cnt4];
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
5E02 花店橱窗
考虑状态设计,由于每种花要依次放置,所以以当前放置的花为阶段,以花瓶和花为状态建立状态表示。
状态表示:d[i,j]表示当前放到第i种花,到达第j个花瓶的最大美观度
转移方程:
对于第j个花瓶,有两种决策:放花和不放花
不放花的情况
放花的情况
边界:
目标:
时间复杂度:
题目还要求记录方案,因此我使用了一个pre1[i,j]和pre2[i,j]记录d[i,j]取到最大值时的上一个状态d[x,y]的两个下标x和y。最后递归输出即可。
代码如下:(ps:和LCIS类似,这题的状态转移方程也有一样的特点,考虑每次随着j的增加 k的范围相对最外层循环只增不减(范围是[i-1,j-1]) 而且每次只增加一个单位。因此可以用变量记录d[i-1][j-1]的取到最优值时j-1的值,从而优化dp。几种方法的具体过程详见代码)
/*
*/
#define method_2
#ifdef method_1
/*
无方案
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int d[maxn][maxn],a[maxn][maxn],f,v;
int main() {
ios::sync_with_stdio(false);
//freopen("花店橱窗.in","r",stdin);
cin>>f>>v;
for(int i=1;i<=f;i++) for(int j=1;j<=v;j++) cin>>a[i][j];
memset(d,-INF,sizeof(d)); //注意答案可能是负数 所以要初始化为-INF 而不是0
for(int i=0;i<=v;i++) d[0][i]=0;
for(int i=1;i<=f;i++){ //为了保证放花的顺序 这里第一重循环是循环花数 即阶段 每个阶段放一束花
for(int j=i;j<=v;j++){
if(j-1>=i) d[i][j]=max(d[i][j-1],d[i][j]);
for(int k=i-1;k<=j-1;k++) d[i][j]=max(d[i][j],d[i-1][k]+a[i][j]);
}
}
cout<<d[f][v];
return 0;
}
#endif
#ifdef method_2
/*
带方案
考虑每次随着j的增加 k的范围相对最外层循环只增不减(范围是[i-1,j-1]) 而且每次只增加一个单位。因此可以用变量记录d[i-1][j-1]的取到最优值时j-1的值,从而优化dp
双重循环 优化dp
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int d[maxn][maxn],a[maxn][maxn],pre1[maxn][maxn],pre2[maxn][maxn],f,v;
void print(int f,int v){
if(pre1[f][v]==0) return;
print(pre1[f][v],pre2[f][v]);
cout<<pre2[f][v]<<" ";
}
int main() {
ios::sync_with_stdio(false);
//freopen("花店橱窗.in","r",stdin);
cin>>f>>v;
for(int i=1;i<=f;i++) for(int j=1;j<=v;j++) cin>>a[i][j];
memset(d,-INF,sizeof(d)); //注意答案可能是负数 所以要初始化为-INF 而不是0
for(int i=0;i<=v;i++) d[0][i]=0;
for(int i=1;i<=f;i++){
int k=i-1;
for(int j=i;j<=v;j++){
d[i][j]=d[i-1][k]+a[i][j];
pre1[i][j]=i-1;
pre2[i][j]=k;
if(d[i-1][j]>d[i-1][k]){
k=j;
}
}
}
int last=0;
for(int i=f;i<=v;i++){
if(d[f][i]>d[f][last]){ //method_2不能保证d[f][v]就是最优解 需要循环找一下 目前原因未知
last=i;
}
}
cout<<d[f][last]<<endl;
print(f,last);
cout<<last;
return 0;
}
#endif
#ifdef method_3
/*
带方案
三重循环
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int d[maxn][maxn],a[maxn][maxn],pre1[maxn][maxn],pre2[maxn][maxn],f,v;
void print(int f,int v){
if(pre1[f][v]==0) return;
print(pre1[f][v],pre2[f][v]);
cout<<pre2[f][v]<<" ";
}
int main() {
ios::sync_with_stdio(false);
//freopen("花店橱窗.in","r",stdin);
cin>>f>>v;
for(int i=1;i<=f;i++) for(int j=1;j<=v;j++) cin>>a[i][j];
memset(d,-INF,sizeof(d)); //注意答案可能是负数 所以要初始化为-INF 而不是0
for(int i=0;i<=v;i++) d[0][i]=0;
for(int i=1;i<=f;i++){
for(int j=i;j<=v;j++){
if(j-1>=i){
if(d[i][j]<d[i][j-1]){
d[i][j]=d[i][j-1];
pre1[i][j]=i;
pre2[i][j]=j-1;
}
}
for(int k=i-1;k<=j-1;k++){
if(d[i][j]<d[i-1][k]+a[i][j]){
d[i][j]=d[i-1][k]+a[i][j];
pre1[i][j]=i-1;
pre2[i][j]=k;
}
}
}
}
cout<<d[f][v]<<endl;
int last;
for(int i=f;i<=v;i++){
if(d[f][i]==d[f][v]){
last=i;
break;
}
}
print(f,last);
cout<<last;
return 0;
}
#endif
POJ1952 Buy Low Buy Lower
LIS的裸题,第一问的状态转移方程不再赘述,这里讲一下第二问怎么求方案。设[1...i]的最长递减子序列的长度为d[i],对应方案数为f[i],则:
但需要注意的是题目中不同方案的定义:两个相同的子序列即使选出的位置不一样,也属于一样的子序列,所以j需要倒序循环,具体原理和反例见代码
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5000+5;
const int INF=0x3f3f3f3f;
int n,a[maxn],d[maxn],f[maxn],ans,ans1;
int main() {
ios::sync_with_stdio(false);
//freopen("Buy Low Buy Lower.in","r",stdin);
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
f[0]=1;
a[0]=INF;
for(int i=1; i<=n; i++) {
d[i]=1;
for(int j=0; j<i; j++) {
if(a[j]>a[i]) d[i]=max(d[i],d[j]+1);
}
/*
//不能这么写 反例
5
3 2 3 1 1
需要输出 3 1
而不是3 2
因为两个最长递减子序列都是3 2 1 所以只能算成一个
for(int j=0;j<i;j++){
if(a[j]>a[i]&&d[i]==d[j]+1) f[i]+=f[j];
}
*/
ans=max(ans,d[i]);
}
for(int i=1; i<=n; i++) {
for(int j=i-1; j>=0; j--) { //倒序循环 不能够顺序进行 反例在上面
if(a[j]>a[i]&&d[i]==d[j]+1) f[i]+=f[j];
if(a[i]==a[j]) break; //相同就break
}
cout<<f[i]<<" ";
}
cout<<endl;
for(int i=1; i<=n; i++) {
// cout<<f[i]<<" ";
if(d[i]==ans) {
ans1+=f[i];
// cout<<i<<" "<<f[i]<<endl;
}
}
// cout<<endl;
cout<<ans<<" "<<ans1;
return 0;
}
POJ1934 Trip
求LCS的过程不再赘述,这里讲一下怎么求方案。
预处理出如下数组
d[i][j]表示s1[1...i]和s2[1...j]的LCS
f[i][j]表示s1[1...i]中的j+'a'最后一次出现的位置
g[i][j]表示s2[1...i]中的j+'a'最后一次出现的位置
然后从最后的状态向前dfs,每次尝试是否选取当前位的字母即可。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int maxm=1000+5;
const int maxl=26+5;
const int INF=0x3f3f3f3f;
int n,m,d[maxn][maxn],f[maxn][maxl],g[maxn][maxl],tot=0;
//d[i][j]表示s1[1...i]和s2[1...j]的LCS
//f[i][j]表示s1[1...i]中的j+'a'最后一次出现的位置
//g[i][j]表示s2[1...i]中的j+'a'最后一次出现的位置
string s1,s2,s[maxm];
void dfs(int len1,int len2,int len,string now) {
if(!len) {
s[++tot]=now;
return;
}
if(!len1||!len2) return;
for(int i=0; i<=25; i++) {
int pos1=f[len1][i],pos2=g[len2][i];
if(d[pos1][pos2]!=len) continue;
dfs(pos1-1,pos2-1,len-1,char(i+'a')+now);//注意不能写成dfs(pos1,pos2,len-1,now+char(i+'a'));
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("Trip.in","r",stdin);
cin>>s1>>s2;
s1=' '+s1,s2=' '+s2;
n=s1.length()-1,m=s2.length()-1;
// for(int i=1;i<=n;i++) cout<<s1[i];
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(s1[i]==s2[j]) d[i][j]=max(d[i][j],d[i-1][j-1]+1);
else d[i][j]=max(d[i][j-1],d[i-1][j]);
}
}
// cout<<d[n][m];
for(int i=1; i<=n; i++) {
for(int j=0; j<=25; j++) {
if(s1[i]==j+'a') f[i][j]=i;
else f[i][j]=f[i-1][j];
}
}
for(int i=1; i<=m; i++) {
for(int j=0; j<=25; j++) {
if(s2[i]==j+'a') g[i][j]=i;
else g[i][j]=g[i-1][j];
}
}
dfs(n,m,d[n][m],"");
sort(s+1,s+tot+1);
for(int i=1; i<=tot; i++) cout<<s[i]<<endl;
return 0;
}
#endif
POJ1722 Substract
假设只有两个数a,b,则只可能产生a-b
假设只有三个数a,b,c,则可能产生a-b-c和a-b+c
假设只有四个数a,b,c,则可能产生a-b-c+d、a-b+c-d、a-b-c-d、a-b+c+d
以此类推,第一个数前一定是'+'号,第二个数前一定是'-'号,其他的数字都可以通过一定的顺序改变前面的符号。
因此,问题等价于求在n个数前面使用加减号使得结果为t的方案,其中第一个数前一定是'+'号,第二个数前一定是'-'号。
因此做出如下状态定义:
状态表示:d[i,j]表示前i个数计算后达到j时,第i个数前的符号。d[i,j]=1表示'+'号,d[i,j]=-1表示'-'号,d[i,j]=0表示未更新或无法达到。
转移方程:
对于第i个数字,有两种决策:前面放'+'号或者'-'号
边界:
目标:
时间复杂度:
这题还有两个注意的地方:
1 由于j可能为负数,所以要做坐标平移
2 考虑输出方案,因为有SPJ,所以可以构造一组合法的解:先去处理所有的加号,相当于把所有的加号都挪去了原来a3的位置,这样最后处理减号的时候,减a2就可以负负得正了。然后处理减号,把所有的减号都挪到了原来a2的位置,给a1来减。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
https://www.cnblogs.com/wyboooo/p/9775701.html
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int base=10100+5;
const int INF=0x3f3f3f3f;
int n,t,a[maxn],d[maxn][base*2+200],ans[maxn];
int main() {
ios::sync_with_stdio(false);
//freopen("Substract.in","r",stdin);
cin>>n>>t;
t+=base;
for(int i=1;i<=n;i++) cin>>a[i];
d[1][a[1]+base]=1;
d[2][a[1]-a[2]+base]=-1;
for(int i=3;i<=n;i++){
for(int j=-10000+base;j<=10000+base;j++){
if(d[i-1][j]){
d[i][j+a[i]]=1,d[i][j-a[i]]=-1;
}
}
}
for(int i=n;i>=2;i--){
ans[i]=d[i][t];
if(ans[i]==-1){
t+=a[i];
}
if(ans[i]==1){
t-=a[i];
}
}
int cnt=0;
for(int i=2;i<=n;i++){ //先处理加号(这里减一次 后面的循环再减一次 就成了加号)
if(ans[i]==1){
cout<<i-cnt-1<<endl;
cnt++;
}
}
for(int i=2;i<=n;i++){
if(ans[i]==-1){
cout<<1<<endl;
}
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ1187 陨石的秘密
题解链接
https://blog.csdn.net/flying_stones_sure/article/details/7954114
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
https://blog.csdn.net/flying_stones_sure/article/details/7954114
dp核心:为了防止一个序列被重复计数,用http://contest-hunter.org:83/contest/0x50%E3%80%8C%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E3%80%8D%E4%BE%8B%E9%A2%98/5302%20%E9%87%91%E5%AD%97%E5%A1%94相同的方法
即每次枚举括号的时候 依次枚举最靠左边外面的括号是()[]还是{}这样在记忆化搜索的时候就不会有重复或遗漏
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxl=15+5;
const int maxd=30+5;
const int mod=11380;
const int INF=0x3f3f3f3f;
int l1,l2,l3,d,f[maxl][maxl][maxl][maxd];
int dfs(int l1,int l2,int l3,int d) {
if((!l1)&&(!l2)&&(!l3)) {
return f[l1][l2][l3][d]=1;
}
if(!d) {
return f[l1][l2][l3][d]=0;
}
if(f[l1][l2][l3][d]) {
return f[l1][l2][l3][d];
}
int res=0;
for(int i=0; i<=l3; i++) {
if(i) res=(res+dfs(0,0,i-1,d-1)*dfs(l1,l2,l3-i,d)%mod)%mod;
for(int j=0; j<=l2; j++) {
if(j) res=(res+dfs(0,j-1,i,d-1)*dfs(l1,l2-j,l3-i,d)%mod)%mod;
for(int k=0; k<=l1; k++) {
if(k) res=(res+dfs(k-1,j,i,d-1)*dfs(l1-k,l2-j,l3-i,d)%mod)%mod;
}
}
}
return f[l1][l2][l3][d]=res;
}
int main() {
ios::sync_with_stdio(false);
//freopen("陨石的秘密.in","r",stdin);
cin>>l1>>l2>>l3>>d;
if(d) cout<<(dfs(l1,l2,l3,d)-dfs(l1,l2,l3,d-1)+mod)%mod;
else cout<<dfs(l1,l2,l3,d)%mod;
//不能写成 else cout<<0; 因为dfs(0,0,0,0)=1
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
5E07 划分大理石
多重背包,但由于只是判断可行性,所以直接照搬POJ1742 Coins就行了。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
可行性dp多重背包 不需要二进制拆分或者单调队列优化
方法参见coin
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=6+5;
const int maxm=200000+5;
const int INF=0x3f3f3f3f;
int a[maxn],f[maxm],used[maxm];
int main() {
ios::sync_with_stdio(false);
// freopen("划分大理石.in","r",stdin);
while(1) {
int flag=0,sum=0;
for(int i=1; i<=6; i++) {
cin>>a[i];
sum+=a[i]*i;
if(a[i]!=0) flag=1;
}
if(!flag) break;
if(sum&1){ //注意这里要特判
cout<<"Can't"<<endl;
continue;
}
sum/=2;
memset(f,0,sizeof(f));
f[0]=1;
for(int i=1;i<=6;i++){
memset(used,0,sizeof(used));
for(int j=i;j<=sum;j++){
if(!f[j]&&f[j-i]&&used[j-i]<a[i]){
f[j]=1,used[j]=used[j-i]+1;
}
}
}
if(f[sum]) cout<<"Can"<<endl;
else cout<<"Can't"<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ2176 Folding
区间DP,讨论两种决策,分割区间和将区间压缩,分别转移即可,具体到实现上,可以借助一个struct来记录[i...j]的最短长度len和对应方案s。利用sprintf和strcpy,strcat转移即可。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int n;
string s;
struct node{
char s[maxn]; //记录方案
int len;
}f[maxn][maxn];
int main() {
ios::sync_with_stdio(false);
//freopen("Folding.in","r",stdin);
cin>>s,s=' '+s,n=s.length();
for(int i=1;i<=n;i++){
f[i][i].len=1,f[i][i].s[0]=s[i];
}
for(int len=2;len<=n;len++){
for(int i=1;i<=n-len+1;i++){
int j=i+len-1;
f[i][j].len=INF;
for(int k=1;k<=len/2;k++){ //贪心原则 让压缩后的子串(除去数字和括号)尽量短 因此从小到大枚举压缩长度
if(len%k) continue;
int l=i,r=i+k;
while(r<=j&&s[l++]==s[r]) r++;
if(r>j){ //可以完全填充[i,j]
sprintf(f[i][j].s,"%d",len/k);
strcat(f[i][j].s,"(");
strcat(f[i][j].s,f[i][i+k-1].s);
strcat(f[i][j].s,")");
f[i][j].len=strlen(f[i][j].s);
break;//贪心原则 让压缩后的子串(除去数字和括号)尽量短
}
}
for(int k=i;k<j;k++){
if(f[i][j].len>f[i][k].len+f[k+1][j].len){
f[i][j].len=f[i][k].len+f[k+1][j].len;
strcpy(f[i][j].s,f[i][k].s);
strcat(f[i][j].s,f[k+1][j].s);
}
}
}
}
cout<<f[1][n].s;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
5E09 能量项链
区间DP,具体细节详见代码。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=200+5;
const int INF=0x3f3f3f3f;
int n,a[maxn],ans=0,d[maxn][maxn];
int main() {
ios::sync_with_stdio(false);
//freopen("能量项链.in","r",stdin);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],a[i+n]=a[i];
for(int len=2;len<=n;len++){
for(int i=1;i<=2*n-len+1;i++){
int j=len+i-1;
for(int k=i;k<j;k++){
d[i][j]=max(d[i][j],d[i][k]+d[k+1][j]+a[i]*a[k+1]*a[j+1]);
//a[i]*a[k+1]*a[j+1]的解释
/*
a[]={0,3,4,5,6,7,8} i=1,j=5,k=2 a[i]=3,a[k]=4,a[k+1]=5,a[j]=7
则此时a分为两段[3,4]和[5,6,7,8]
相当于两端珠子(3,4)(4,5)和(5,6)(6,7)(7,8)
分别合并后两端珠子变成(3,5)和(5,8)
合并后的珠子为(3,8) 这一次合并放出的能量是3*5*8=a[1]*a[3]*a[6]=a[i]*a[k+1]*a[j+1]
*/
}
}
}
for(int i=1;i<=n+1;i++){
ans=max(ans,d[i][i+n-1]);
}
cout<<ans;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ1191 棋盘分割
化简均方差公式
因此,我们发现,为定值,所以只考虑计算,其中为第i个矩形的元素和。
因此用一个五维dp数组进行递推即可,代码里有博客链接,那里有关于状态定义,状态转移方程和初值的详解。
代码如下
/*
注意题目要求 ——使各矩形棋盘总分的均方差最小
公式中xi为第i块矩形棋盘的总分 而不是某个矩形的第i个元素!
因此在dp的时候 dp初态是矩形各个元素的和的平方 而不是平方和!
https://www.cnblogs.com/scau20110726/archive/2013/02/27/2936050.html
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=15+2;
const int maxl=8+2;
const int INF=0x3f3f3f3f;
double d[maxn][maxl][maxl][maxl][maxl],s[maxl][maxl];
int n;
double cal(int i,int j,int k,int l) {
double ans=s[k][l]-s[k][j-1]-s[i-1][l]+s[i-1][j-1];
return ans*ans;
}
int main() {
ios::sync_with_stdio(false);
//freopen("棋盘分割.in","r",stdin);
scanf("%d",&n);
for(int i=1; i<=8; i++) {
for(int j=1; j<=8; j++) {
scanf("%lf",&s[i][j]);
s[i][j]=s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
}
for(int m=1; m<=n; m++)
for(int i=1; i<=8; i++) {
for(int j=1; j<=8; j++) {
for(int k=i; k<=8; k++) {
for(int l=j; l<=8; l++) {
if(m==1) d[1][i][j][k][l]=cal(i,j,k,l);
else d[m][i][j][k][l]=1<<30;
}
}
}
}
// printf("%lf\n",cal(1,2,1,2));
for(int m=2; m<=n; m++) {
for(int i=1; i<=8; i++) {
for(int j=1; j<=8; j++) {
for(int k=i; k<=8; k++) {
for(int l=j; l<=8; l++) {
double &temp=d[m][i][j][k][l];
for(int x1=i; x1<k; x1++) { //注意x1的范围
temp=min(temp,d[m-1][i][j][x1][l]+cal(x1+1,j,k,l));
temp=min(temp,d[m-1][x1+1][j][k][l]+cal(i,j,x1,l));
//由于存在顺序问题 所以要选一个作为不会再切的矩形
//如果这里只有一行 会wa
}
for(int x2=j; x2<l; x2++) {
temp=min(temp,d[m-1][i][j][k][x2]+cal(i,x2+1,k,l));
temp=min(temp,d[m-1][i][x2+1][k][l]+cal(i,j,k,x2));
}
}
}
}
}
}
printf("%.3lf",sqrt(d[n][1][1][8][8]/n-(s[8][8]/n)*(s[8][8]/n)));
return 0;
}
POJ1390 Blocks
首先用一个结构体,来记录一个个方块组的长度和颜色。
显然单个的一个方块组可以视为一个长度为1的区间,可以作为区间dp的边界。
之后考虑状态定义:
如果只是用状态d[i,j]来描述消去方块i到方块j获得的分数是无法形成递推关系的。 因为在这个时候对于最右边的大块有两种选择,一是直接消去,二是将其与左边某个大块 合并删除。而对于选择二来说,删去未必是最有方案,也许还应该与左边的某方块合并后 消去。所以只有两个参数是无法准确描述状态并形成递推关系的。
因此附加一个参数来维护状态:
d[l,r,len]表示消去方块组l至r,同时r右边与r同色的方块长度(也称之为个数)为len。
此时递推关系:
直接消去r:
将j与左边某个方块k合并:
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
https://blog.csdn.net/qq_29169749/article/details/52202149
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=200+5;
const int INF=0x3f3f3f3f;
int d[maxn][maxn][maxn],n,a[maxn],t,kase=0,cnt;
struct Segment{
int c,l;
}b[maxn];
int dfs(int l,int r,int len){
if(l>r) return 0;
if(l==r) return (b[l].l+len)*(b[l].l+len);
if(d[l][r][len]!=-1) return d[l][r][len];
int ans=dfs(l,r-1,0)+(b[r].l+len)*(b[r].l+len);
for(int k=l;k<r;k++){
if(b[r].c==b[k].c){
ans=max(ans,dfs(k+1,r-1,0)+dfs(l,k,b[r].l+len));
}
}
return d[l][r][len]=ans;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Blocks.in","r",stdin);
cin>>t;
while(t--){
cout<<"Case "<<++kase<<": ";
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
memset(d,-1,sizeof(d));
cnt=1;
for(int i=1;i<=n;i++){
if(a[i]==a[i-1]){
b[cnt].l++;
}
else{
b[++cnt].c=a[i];
b[cnt].l=1;
}
}
cout<<dfs(1,cnt,0)<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ1463 Strategic game
很基础的树形dp,每个节点有两个状态,跑一次dfs即可。
但是需要注意的是,这里要求的是看守所有的“边”。也就是说,每条边至少有一个端点存在守卫,因此每个点状态只可能是如下两个状态之一:该节点放置守卫来守卫这个点到其子节点的边,或者该节点不放置守卫,但靠在所有子节点放置守卫来守卫这个点到其子节点的边。
但如果是要守卫树上的所有的“点”,那么就不能做这样简单的状态定义了。因为每个点可以有三种状态:被父亲守卫,被自己守卫,被儿子守卫。具体转移方程参见vijos 1144小胖守皇宫。
本题代码如下
/*
*/
#define method_1
#ifdef method_1
/*
和vijos 1144不同 那道题目要求守卫所有点 因此每个点有三种守卫情况:被自己守卫 被儿子守卫 被父亲守卫 所以状态分三种
换句话说 就是会出现某些边不会被覆盖的情况 反例见method_2
https://www.cnblogs.com/linda-fcj/p/7206257.html
但是这道题目要求的是 守卫所有边 每条边有两个端点 因此只有两种状态:被父端点守卫 被子端点守卫
因此设f[x][0]表示守卫以x节点为根的子树 x节点不放置士兵的最小代价
f[x][1]表示守卫以x节点为根的子树 x节点放置士兵的最小代价
转移一下就行了
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1500+5;
const int INF=0x3f3f3f3f;
int n,f[maxn][2],deg[maxn];
vector<int>son[maxn];
void dfs(int x) { //flag=0 靠自己保护 flag=1 靠儿子保护
f[x][0]=0,f[x][1]=1;
for(int i=0; i<son[x].size(); i++) {
int y=son[x][i];
dfs(y);
f[x][0]+=f[y][1];
f[x][1]+=min(f[y][0],f[y][1]);
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("Strategic game.in","r",stdin);
while(~scanf("%d",&n)) {
memset(deg,0,sizeof(deg));
for(int i=0; i<=n-1; i++) son[i].clear();
int now,num,temp;
for(int i=0; i<=n-1; i++) {
scanf("%d:(%d)",&now,&num);
for(int j=0; j<=num-1; j++) {
scanf("%d",&temp);
son[now].push_back(temp);
deg[temp]++;
// son[temp].push_back(now);
}
}
for(int i=0; i<=n-1; i++) {
if(!deg[i]) {
dfs(i);
cout<<min(f[i][0],f[i][1])<<endl;
break;
}
}
}
return 0;
}
#endif
#ifdef method_2
/*
魔改后的vijos 1144的代码 只过了两个点
反例如下
6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 10 0
6 5 0
应该选择3 4 5 6四个点 得到答案24
但是这个程序会输出25
原因在于 最后方案下 1->2的边两端都没有被覆盖
但是这时 所有顶点都是被覆盖到的
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1500+5;
const int INF=0x3f3f3f3f;
int n,f[maxn][2],deg[maxn],a[maxn];
vector<int>son[maxn];
void dfs(int x) { //flag=0 靠自己保护 flag=1 靠儿子保护
f[x][0]=0,f[x][1]=a[x];
for(int i=0; i<son[x].size(); i++) {
int y=son[x][i];
dfs(y);
f[x][0]+=f[y][1];
f[x][1]+=min(f[y][0],f[y][1]);
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("Strategic game.in","r",stdin);
scanf("%d",&n);
int pos,now,num,temp;
for(int i=1; i<=n; i++) {
scanf("%d",&pos);
scanf("%d%d",&a[pos],&num);
for(int j=0; j<=num-1; j++) {
scanf("%d",&temp);
son[pos].push_back(temp);
deg[temp]++;
// son[temp].push_back(now);
}
}
for(int i=1; i<=n; i++) {
if(!deg[i]) {
dfs(i);
cout<<min(f[i][0],f[i][1])<<endl;
break;
}
}
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
网友评论