T1
题目:codevs4815江哥的dp题a
codevs4815
一个简单的DP,注意开long long(不然会全WA),以及初始条件(这题有负数,所以要把f设成极小值.还要保证转移正确).
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
const int maxN = 1000 + 7;
using namespace std;
ll f[maxN][maxN][2],w[maxN];
int main() {
ll n,k;
memset(f,-63,sizeof(f));
scanf("%lld%lld",&n,&k);
for(int i = 1;i <= n;++ i)
scanf("%lld",&w[i]);
for(int i = 0;i <= n;++ i) f[i][0][0] = 0;
for(int i = 1;i <= n;++ i) {
for(int j = 1;j <= k;++ j) {
f[i][j][0] = max(f[i - 1][j][0],f[i - 1][j][1]);
f[i][j][1] = max(f[i - 1][j - 1][0] + w[i],f[i][j][1]);
}
}
printf("%lld",max(f[n][k][0],f[n][k][1]));
}
T2
题目:codevs1695 windows 2013
codevs1695
简单的DP,和上一个题差不多.注意题目中的开头先用
#include <iostream>
#include <cstring>
#include <cstdio>
#define ll long long
const int maxN = 100 + 7;
using namespace std;
ll f[maxN][2],a[maxN],b[maxN],c[maxN],n;//f[i][0]当前用勺 f[i][1]当前用筷
int main() {
memset(f,0x3f,sizeof(f));
scanf("%lld",&n);
for(int i = 1;i <= n;++ i)
scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);//勺子筷子i道菜a_i,b_i。交换c_i
f[1][1] = b[1];
f[1][0] = c[1] + a[1];
for(int i = 2;i <= n;++ i) {
f[i][0] = min(f[i - 1][1] + c[i] + a[i],f[i - 1][0] + a[i]);
f[i][1] = min(f[i - 1][0] + c[i] + b[i],f[i - 1][1] + b[i]);
}
printf("%lld",min(f[n][0],f[n][1]));
return 0;
}
luogu2066 机器分配
题目链接:luogu2066
设状态f[i][j]表示第i个公司分配j台的最佳答案.那么就由dp转移方程.
dp[i][j] =dp[i - 1][j - k] + w[i][k];
输出路径,用一个数组存下路径就OK了.这里要注意的是按字典序进行输出,.
#include <iostream>
#include <cstdio>
#include <queue>
#define ll long long
const int maxN = 20;
const int maxM = 20;
using namespace std;
queue<ll>q;
ll n,m;
ll w[maxN][maxM],f[maxN][maxM],path[maxN][maxM][maxN];
int main() {
scanf("%lld%lld",&n,&m);
for(int i = 1;i <= n;++ i ){
for(int j = 1;j <= m;++ j) {
scanf("%lld",&w[i][j]);
}
}
for(int i = 1;i <= n;++ i ) {
for(int j = 0;j <=m ;++ j ) {
for(int k = 0;k <= j;++ k) {
if(f[i - 1][k] + w[i][j - k] > f[i][j]) {
f[i][j] = f[i - 1][k] + w[i][j - k];
for(int l = 1;l < i;l ++ )path[i][j][l] = path[i - 1][k][l];
path[i][j][i] = j - k;
}
}
}
}
printf("%d
",f[n][m]);
for(int i=1;i<=n;i++) cout<<i<<" "<<path[n][m][i]<<endl;
return 0;
}
luogu 1564膜拜
luogu1564
先求出i - j人数差.设f[i]表示前i人最少的分配的数,然后就有dp方程
f[i] = min(f[i],f[j] + 1)(j满足一定的条件)
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,a[2501],b[2501],f[2501];
int main()
{
int i;
scanf("%d%d",&n,&m);
for(i=1,x;i<=n;i++)
{
scanf("%d",&x);
if(x == 1)
a[i] = a[i - 1] + 1,b[i] = b[i - 1];
else
a[i] = a[i - 1],b[i] = b[i - 1] + 1;
}
for(i = 1;i <= n;i ++)
{
f[i] = i;
for(j = i;j >= 0;j --)
if(a[i] - a[j] == i - j || b[i] - b[j] == i - j || abs(b[i] - b[j] - a[i] + a[j]) <= m)
f[i] = min(f[i],f[j]+1);
}
printf("%d",f[n]);
return 0;
}
luogu1115最大字段和
luogu1115
f[i]表示第i个位置的最大字段和.然后得转移方程:f[i] = max(f[i - 1] + a[i],a[i])
用一个变量不断地记录maxn
#include <iostream>
#include <cstdio>
#include <cstring>
const int maxN = 200000 + 7;
using namespace std;
int f[maxN],maxn = -0x7fffffff,a[maxN];
int main() {
int n;
scanf("%d",&n);
for(int i = 1;i <= n;++ i )
scanf("%d",&a[i]);
for(int i = 1;i <= n;++ i) {
f[i] = max(f[i - 1] + a[i],a[i]);
maxn = max(f[i],maxn);
}
printf("%d",maxn);
return 0;
}
poj2479 -- Maximum sum
poj2479
正反两边最大子段和,然后枚举断点即可.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxN = 50000 + 7;
int f[maxN],a[maxN],dp[maxN],qwq[maxN],qaq[maxN];
int main() {
int T,n;
scanf("%d",&T);
while(T --) {
int Ans = -0x7fffffff;
scanf("%d",&n);
memset(f,0,sizeof(f));
memset(dp,0,sizeof(dp));
memset(qwq,0,sizeof(qwq));
memset(qaq,0,sizeof(qaq));
for(int i = 1;i <= n;++ i)
scanf("%d",&a[i]);
for(int i = 1;i <= n;++ i)
f[i] = max(f[i - 1] + a[i],a[i]),qwq[i] = max(f[i],qwq[i - 1]);
for(int j = n;j >= 1; -- j)
dp[j] = max(dp[j + 1] + a[j],a[j]),qaq[j] = max(dp[j],qaq [j - 1]);
for(int i = 1;i <= n;++ i) {
Ans = max(Ans,qwq[i] + qaq[i + 1]);
}
printf("%d
",Ans);
}
}