题意： m个不重叠的区间的 最大值
dp[i][j]表示 在确保 第j 个数在的情况下分成 i 组的情况， 所以存在两种情况，第j个数与前
dp[i][j-1]一起 或者 dp[i-1][k] 一起单独成区间
dp[i][j]=max(dp[i][j-1]+max(dp[i-1][k]))+a[j]
k的取值为 （i-1）~j
而max(dp[i-1][k]) 表示上一次求得的值 ，而dp只与上一次 有关，并记录上一次的最大值即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 1000003
ll dp[maxn][2];
ll sum[maxn];
int main()
{
ll m,n;
ll t;
while(cin>>m>>n)
{
sum[0]=0;
dp[0][0]=0;
dp[0][1]=0;
for(int i=1;i<=n;i++)
{
cin>>t;
sum[i]=sum[i-1]+t;
dp[i][0]=0;
dp[i][1]=0;
}
ll ans=0;
for(int i=1;i<=m;i++)
{
ans=-327670000005;
for(int j=i;j<=n;j++)
{
// cout<<dp[j-1][0]<<" "<<dp[j-1][1]<<" "<<(sum[j]-sum[j-1])<<endl;
dp[j][1]=max(dp[j-1][1],dp[j-1][0])+sum[j]-sum[j-1];
dp[j-1][0]=ans;
ans=max(ans,dp[j][1]);
}
}
cout<<ans<<endl;
}
return 0;
}
题意：输出 超过 一半的数 是什么？
水题吧
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,int>mapp;
int main()
{
int n;
ll t;
while(scanf("%d",&n)!=EOF)
{
ll ui=0;
mapp.clear();
for(int i=0;i<n;i++)
{
scanf("%lld",&t);
mapp[t]++;
if(mapp[t]==(n+1)/2)
{
ui=t;
//break;
}
}
cout<<ui<<endl;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node{
int x;
int y;
int z;
};
Node node[200];
int height[200];
bool cmp(Node a,Node b)
{
if(a.x==b.x)
{
if(b.y==a.y)
{
return a.z>b.z;
}
return a.y>b.y;
}
return a.x>b.x;
}
int main()
{
int n;
int x,y,z;
int t=1;
while(scanf("%d",&n)!=EOF&&n)
{
memset(height,0,sizeof(height));
for(int i=0;i<n;i++)
{
cin>>x>>y>>z;
node[i*6].x=x;
node[i*6].y=y;
node[i*6].z=z;
node[i*6+1].x=x;
node[i*6+1].y=z;
node[i*6+1].z=y;
node[i*6+2].x=y;
node[i*6+2].y=x;
node[i*6+2].z=z;
node[i*6+3].x=y;
node[i*6+3].y=z;
node[i*6+3].z=x;
node[i*6+4].x=z;
node[i*6+4].y=y;
node[i*6+4].z=x;
node[i*6+5].x=z;
node[i*6+5].y=x;
node[i*6+5].z=y;
}
sort(node,node+6*n,cmp);
height[0]=node[0].z;
int ans=height[0];
for(int i=0;i<n*6;i++)
{
height[i]=node[i].z;
}
for(int i=0;i<n*6;i++)
{
for(int j=i+1;j<n*6;j++)
{
if(node[i].x>node[j].x&&node[i].y>node[j].y)
{
if(height[j]<height[i]+node[j].z)
height[j]=height[i]+node[j].z;
// cout<<i<<" "<<j<<" "<<height[j]<<endl;
ans=max(ans,height[j]);
}
}
}
cout<<"Case "<<(t++)<<": maximum height = "<<ans<<endl;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int pre[40000];
int dp[40000];
struct Node{
string a;
int et;
int lt;
};
Node node[16];
int t[40000];
void print(int x)
{
if(x==0)
{
return ;
}
else
{
print(x-(1<<pre[x]));
}
cout<<node[pre[x]].a<<endl;
}
int main()
{
int n;
int cn;
int tn;
cin>>tn;
while(tn--)
{
cin>>n;
memset(t,0,sizeof(t));
memset(dp,0,sizeof(dp));
memset(pre,-1,sizeof(pre));
for(int i=0;i<=n;i++)
{
pre[i]=i;
}
for(int i=0;i<n;i++)
{
cin>>node[i].a>>node[i].et>>node[i].lt;
}
//i 表示状态
for(int i=1;i<(1<<n);i++)
{
dp[i]=1000000000;
for(int j=n-1;j>=0;j--)
{
int temp=(1<<j);
// i中没有 这个作业的话
if(!(i&temp))
{
continue;
}
int score=t[i-temp]+node[j].lt-node[j].et;
if(score<0)
{
score=0;
}
if(dp[i]>dp[i-temp]+score)
{
dp[i]=dp[i-temp]+score;
t[i]=t[i-temp]+node[j].lt;
pre[i]=j;
}
}
}
cout<<dp[(1<<n)-1]<<endl;
print((1<<n)-1);
}
return 0;
}
[kuangbin]https://www.cnblogs.com/xiong-/p/4093962.html()
最大递增 子序列 的和 ，dp 复杂度为 n^2 上面的链接中提供了 nlongn 线段树的解法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll num[1001];
ll ans[1001];
ll en;
int main()
{
int n;
while(cin>>n&&n)
{
for(int i=0;i<n;i++)
{
cin>>num[i];
ans[i]=num[i];
}
int a,b;
a=b=0;
ll temp=num[0];
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(num[j]<num[i])
{
if(ans[j]+num[i]>ans[i])
{
ans[i]=ans[j]+num[i];
}
}
}
temp=max(temp,ans[i]);
}
cout<<temp<<endl;
}
return 0;
}
题意： 装满的完全背包 价值最低是多少
说起背包问题 不得不说 崔添翼的背包九讲 讲得实在是太好了太好了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 5000003
ll dp[maxn];
struct Node{
ll w;
ll v;
};
Node node[501];
int main()
{
int t;
cin>>t;
ll ee,ff;
while(t--)
{
cin>>ee>>ff;
ee=ff-ee;
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>node[i].v>>node[i].w;
}
fill(dp,dp+ee+1,maxn);
ll ans=maxn;
for(int i=0;i<n;i++)
{
dp[node[i].w]=min(dp[node[i].w],node[i].v);
}
for(int i=0;i<n;i++)
{
for(int j=0;j<=ee;j++)
{
if(j>=node[i].w&&dp[j-node[i].w]!=maxn)
{
if(dp[j]==maxn)
{
dp[j]=dp[j-node[i].w]+node[i].v;
}
else
dp[j]=min(dp[j],dp[j-node[i].w]+node[i].v); //无限 完全 背包 最小
}
// 无限 完全 背包 最大
//dp[j]=max(dp[j],dp[j-node[i].w]+node[i].v);
}
}
if(dp[ee]==maxn)
{
cout<<"This is impossible."<<endl;
}
else
{
cout<<"The minimum amount of money in the piggy-bank is "<<dp[ee]<<"."<<endl;
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 5000003
int mapp[13][100002];
bool vis[13][100002];
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int t;
int a,b;
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
break;
memset(mapp,0,sizeof((mapp)));
memset(vis,0,sizeof(vis));
t=0;
for(int i=0;i<n;i++)
{
scanf("%d %d",&a,&b);
mapp[a+1][b]++;
t=max(t,b);
}
int ans=0;
vis[6][0]=1;
for(int i=1;i<=t;i++)
{
int temp=0;
for(int j=1;j<12;j++)
{
// cout<<mapp[j][i];
if(vis[j][i-1])
{
temp=mapp[j][i-1]+mapp[j][i];
vis[j][i]=1;
}
if(j>1&&vis[j-1][i-1])
{
temp=max(temp,(mapp[j-1][i-1]+mapp[j][i]));
vis[j][i]=1;
}
if(j<11&&vis[j+1][i-1])
{
temp=max((mapp[j+1][i-1]+mapp[j][i]),temp);
vis[j][i]=1;
}
if(vis[j][i])
{
mapp[j][i]=temp;
ans=max(mapp[j][i],ans);
}
}
}
printf("%d\n",ans);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define maxn 101
int n1[2001];
int n2[2001];
int dp[2001][2];
int main()
{
// freopen("input.txt","r",stdin);
int n;
int t;
cin>>t;
int a,b;
while(t--)
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>n1[i+1];
}
for(int i=0;i<n-1;i++)
{
cin>>n2[i+1];
}
for(int j=0;j<=2000;j++)
{
dp[j][0]=25000;
dp[j][1]=25000;
}
dp[1][0]=n1[1];
dp[0][0]=0;
dp[0][1]=0;
for(int i=2;i<=n;i++)
{
dp[i][0]=min(dp[i-1][0],dp[i-1][1])+n1[i];
dp[i][1]=min(dp[i-2][0],dp[i-2][1])+n2[i-1];
}
int ans=min(dp[n][0],dp[n][1]);
//cout<<ans<<endl;
int h=ans/3600;
int fen=ans%3600/60;
int seco=ans%60;
h+=8;
int f=0;
if(h>=12)
{
f=1;
}
if(f==0)
{
printf("%02d:%02d:%02d am\n",h,fen,seco);
}
else
{
printf("%02d:%02d:%02d pm\n",h,fen,seco);
}
}
return 0;
}
贪心？
#include <bits/stdc++.h>
using namespace std;
#define maxn 101
int n1[2001];
vector<int>v;
int main()
{
//freopen("input.txt","r",stdin);
int n;
int t;
int a,b;
int ans=0;
while(cin>>n)
{
v.clear();
ans=0;
for(int i=1;i<=n;i++)
{
cin>>n1[i];
}
for(int i=1;i<=n;i++)
{
int f=0;
sort(v.begin(),v.end());
for(int j=0;j<v.size();j++)
{
if(v[j]>=n1[i])
{
f=1;
v[j]=n1[i];
break;
}
}
if(f==0)
{
// cout<<n1[i]<<endl;
ans++;
v.push_back(n1[i]);
}
}
cout<<ans<<endl;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define maxn 101
int n1[2001];
vector<int>v;
struct Node{
int w;
int s;
int id;}node[1001];
int c[1001];
int dp[1001];
bool cmp(Node a,Node b)
{
if(a.w==b.w)
{
return a.s>b.s;
}
return a.w<b.w;
}
void pr(int ff,int cn)
{
if(cn<=0)
return;
else
{
pr(c[ff],cn-1);
cout<<node[ff].id<<endl;
}
}
int main()
{
// freopen("input.txt","r",stdin);
int n=0;
int t;
int a,b;
int ans=1;
while(cin>>node[n].w>>node[n].s)
{
node[n++].id=n;
}
sort(node,node+n,cmp);
int temp=1;
int f=1;
dp[0]=1;
int mf=0;
for(int i=1;i<n;i++)
{
f=-1;
temp=1;
for(int j=0;j<i;j++)
{
if(node[j].w<node[i].w&&node[j].s>node[i].s)
{
if(temp<dp[j]+1)
{
f=j;
temp=dp[j]+1;
}
}
}
dp[i]=temp;
if(ans<dp[i])
{
ans=dp[i];
mf=i;
}
c[i]=f;
}
cout<<ans<<endl;
pr(mf,ans);
return 0;
}
L poj 1458
最长公共子序列
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
#define maxn 201
int ma[1000][1000];
int main()
{
//freopen("input.txt","r",stdin);
int cn=0;
string s1,s2;
while(cin>>s1>>s2)
{
memset(ma,0,sizeof(ma));
for(int i=0;i<s2.size();i++)
{
for(int j=0;j<s1.size();j++)
{
if(s2[i]==s1[j])
{
ma[i+1][j+1]=ma[i][j]+1;
}
else
{
ma[i+1][j+1]=max(ma[i][j+1],ma[i+1][j]);
// cout<<"2 : "<<i<<" "<<j<<" "<<ma[i][j]<<endl;
}
}
}
cout<<ma[s2.size()][s1.size()]<<endl;
}
return 0;
}
最长公共子序列长度
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
#define maxn 201
int ma[1000];
int dp[1000];
int main()
{
//freopen("input.txt","r",stdin);
int n=0;
string s1,s2;
while(cin>>n)
{
int ans=1;
for(int i=0;i<n;i++)
{
cin>>ma[i];
}
for(int i=0;i<n;i++)
{
dp[i]=1;
for(int j=0;j<i;j++)
{
if(ma[i]>ma[j])
{
if(dp[i]<dp[j]+1)
{
dp[i]=dp[j]+1;
ans=max(dp[i],ans);
}
}
}
}
cout<<ans<<endl;
}
return 0;
}
