A BZOJVIP 1642
Discription
贝茜是一只非常努力工作的奶牛，她总是专注于提高自己的产量。为了产更多的奶，她预计好了接下来的N (1 ≤ N ≤ 1,000,000)个小时，标记为0…N-1。 Farmer John 计划好了 M (1 ≤ M ≤ 1,000) 个可以挤奶的时间段。每个时间段有一个开始时间(0 ≤ 开始时间 ≤ N), 和一个结束时间 (开始时间 < 结束时间 ≤ N), 和一个产量 (1 ≤ 产量 ≤ 1,000,000) 表示可以从贝茜挤奶的数量。Farmer John 从分别从开始时间挤奶，到结束时间为止。每次挤奶必须使用整个时间段。 但即使是贝茜也有她的产量限制。每次挤奶以后，她必须休息 R (1 ≤ R ≤ N) 个小时才能下次挤奶。给定Farmer John 计划的时间段，请你算出在 N 个小时内，最大的挤奶的量。
Input
第1行三个整数N，M，R.接下来M行，每行三个整数Si，Ei，Pi．
Output
最大产奶量．
Sample Input12 4 2
1 2 8
10 12 19
3 6 24
7 10 31
Sample Output
43
Hint
注意：结束时间不挤奶
//排序后dp
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node{
int x,y,z;
}a[1005];
int dp[1005];
int m,n,r,ans=-1;
int ma(int a,int b){return a>b?a:b;}
bool cmp(node a,node b){
if(b.x==a.x) return a.y<b.y;
return a.x<b.x;
}
int main(){
while(scanf("%d%d%d",&n,&m,&r)!=EOF){
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
a[i].y+=r;
}
sort(a+1,a+m+1,cmp);
memset(dp,0,sizeof(dp));
int tem,i,j,k;
for(i=1;i<=m;i++){
dp[i]=a[i].z;
for(int j=1;j<i;j++){
if(a[i].x>=a[j].y)
dp[i]=ma(dp[j]+a[i].z,dp[i]);
}
//printf("%d %d %d\n",i,a[i].y,dp[a[i].y]);
ans=ma(dp[i],ans);
}
printf("%d\n",ans);
}
return 0;
}
B CodeForces 366C
Discription
Dima, Inna and Seryozha have gathered in a room. That’s right, someone’s got to go. To cheer Seryozha up and inspire him to have a walk, Inna decided to cook something.
Dima and Seryozha have n fruits in the fridge. Each fruit has two parameters: the taste and the number of calories. Inna decided to make a fruit salad, so she wants to take some fruits from the fridge for it. Inna follows a certain principle as she chooses the fruits: the total taste to the total calories ratio of the chosen fruits must equal k. In other words, , where aj is the taste of the j-th chosen fruit and bj is its calories.
Inna hasn’t chosen the fruits yet, she is thinking: what is the maximum taste of the chosen fruits if she strictly follows her principle? Help Inna solve this culinary problem — now the happiness of a young couple is in your hands!
Inna loves Dima very much so she wants to make the salad from at least one fruit.
Input
The first line of the input contains two integers n, k(1 ≤ n ≤ 100, 1 ≤ k ≤ 10). The second line of the input contains n integers a1, a2, …, an(1 ≤ ai ≤ 100) — the fruits’ tastes. The third line of the input contains n integers b1, b2, …, bn(1 ≤ bi ≤ 100) — the fruits’ calories. Fruit number i has taste ai and calories bi.
Output
If there is no way Inna can choose the fruits for the salad, print in the single line number -1. Otherwise, print a single integer — the maximum possible sum of the taste values of the chosen fruits.
Sample Input Input
3 2
10 8 1
2 7 1
Output
18
Input
5 3
4 4 4 4 4
2 2 2 2 2
Output
-1
公式变形后的01背包题，只不过体积有负数，要注意，有两种做法规避，一种分正负dp两次，一种放大全变成正数
//放大
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define inf 0xcf
int dp[101][201000],n,k;
int a[111],b[111],c[111];
int ma(int a,int b){return a>b?a:b;}
int main(){
while(scanf("%d%d",&n,&k)!=EOF){
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++) c[i]=a[i]-k*b[i];
memset(dp,inf,sizeof(dp));
dp[0][1000*n]=0;
for(int i=1;i<=n;i++)
for(int j=2000*n;j>=c[i]&&j>=0;j--){
dp[i][j]=ma(dp[i-1][j],dp[i-1][j-c[i]]+a[i]);
//printf("%d %d %d\n",i,j,dp[j]);
}
if(dp[n][n*1000]<=0)
printf("-1\n");
else
printf("%d\n",dp[n][n*1000]);
}
return 0;
}
C -CF544C
** 完全背包**
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 555
int a[N],m,n,mod,b;
int dp[N][N];
int main(){
scanf("%d%d%d%d",&n,&m,&b,&mod);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
dp[0][0]=1;
for(int i=0;i<n;i++){
for(int j=1;j<=m;j++){
for(int k=a[i];k<=b;k++){
dp[j][k]=(dp[j][k]+dp[j-1][k-a[i]])%mod;
//printf("%d %d %d\n",j,k,dp[j][k]);
}
}
}
int ans=0;
for(int i=0;i<=b;i++)
ans=(ans+dp[m][i])%mod;
printf("%d\n",ans);
return 0;
}
D-BZOJ1616
**数字三角形，直接遍历tmn
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 111
char ma[N][N];
int m,n,t,dp[20][N][N],a,b,c,d;
int x[4]={0,0,1,-1},y[4]={1,-1,0,0};
int main(){
while(scanf("%d%d%d",&m,&n,&t)!=EOF){
for(int i=0;i<m;i++)
scanf(" %s",&ma[i]);
scanf("%d%d%d%d",&a,&b,&c,&d);
memset(dp,0,sizeof(dp));
dp[0][a-1][b-1]=1;
for(int s=1;s<=t;s++)
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(ma[i][j]=='.')
for(int k=0;k<4;k++){
int xx=i+x[k],yy=j+y[k];
if(xx>=0&&yy>=0&&xx<m&&yy<n)
dp[s][i][j]+=dp[s-1][xx][yy];
//printf("%d %d %d %d\n",s,i,j,dp[s][i][j]);
}
printf("%d\n",dp[t][c-1][d-1]);
}
return 0;
}E-CF1197D
dp不是很懂
/*对于每个元素都有m种状态，当前元素在不同状态对后面的影响是不同的，所以我们可以开一个n* m大小的dp数组dp[i][j]，代表第i个元素，在长度对m取模后的j位置时的最大值。
状态转移方程为
（j == 1）dp[i][j] = max(a[i] - k, dp[i - 1][m] + a[i] - k);
（j > 1）dp[i][j] = dp[i - 1][j - 1] + a[i];
*/
#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
ll a[N];
ll dp[N][20];
ll ma(ll a,ll b){return a>b?a:b;}
int main()
{
int n, m, k;
scanf("%d%d%d",&n,&m,&k);
a[0] = 0;
for (int i = 1; i <= m; i ++)dp[0][i] = -1e10;
ll ans = 0;
for (int i = 1; i <= n; i ++){
scanf("%lld", &a[i]);
for (int j = 1; j <= m; j ++){
if (j == 1)dp[i][j] = ma(a[i] - k, dp[i - 1][m] + a[i] - k);
else dp[i][j] = dp[i - 1][j - 1] + a[i];
ans = ma(ans, dp[i][j]);
}
}
printf("%lld\n", ans);
return 0;
}F-CF583D LIS变形
分t<=n和t>n两种情况就可以了，具体看代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int a[33333],dp[33333],num,n,t,cnt[333];
int ma(int a,int b){return a>b?a:b;}
int mi(int a,int b){return a<b?a:b;}
int main(){
scanf("%d %d",&n,&t);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
num=ma(num,++cnt[a[i]]);
}
int l=mi(n,t)*n;
int ans=0;
for(int i=n;i<l;i++)
a[i]=a[i-n];
for(int i=0;i<l;i++){
dp[i]=1;
for(int j=i-1;j>=ma(i-n,0);j--){
if(a[i]>=a[j])
dp[i]=ma(dp[i],dp[j]+1);
}
ans=ma(dp[i],ans);
}
if(t<=n) printf("%d\n",ans);
else printf("%d\n",ans+num*(t-n));
return 0;
}G-CF10D
LCIS
//（转，待补）
/*dp[i][j]表示。处理完A序列的前i个，且上升序列以B序列的B[j]结尾的最长子序列。感觉这个把状态体现以什么结尾是很不错的思想。然后转移显而易见了。
if(A[i]==B[j])
dp[i][j]=dp[i-1][k];//k是小于j且B[k]<B[j]
else
dp[i][j]=dp[i-1][j];
我们可以i,j循环这样就可以省掉找k的时间。复杂度O(n*m)
*/
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
int dp[550][550],A[550],B[550],path[550][550],n,m;
bool print(int x)
{
if(!x)
return false;
if(print(path[n][x]))
printf(" %d",B[x]);
else
printf("%d",B[x]);
return true;
}
int main()
{
int i,j,tp,ans,pos;
while(~scanf("%d",&n))
{
for(i=1;i<=n;i++)
scanf("%d",&A[i]);
scanf("%d",&m);
for(i=1;i<=m;i++)
scanf("%d",&B[i]);
memset(dp,0,sizeof dp);
for(i=1;i<=n;i++)
{
tp=pos=0;
for(j=1;j<=m;j++)
{
dp[i][j]=dp[i-1][j];
path[i][j]=path[i-1][j];
if(A[i]==B[j]&&tp+1>dp[i][j])
dp[i][j]=tp+1,path[i][j]=pos;
if(B[j]<A[i]&&dp[i-1][j]>tp)
tp=dp[i-1][j],pos=j;
}
}
ans=1;
for(i=1;i<=m;i++)
if(dp[n][i]>dp[n][ans])
ans=i;
printf("%d\n",dp[n][ans]);
if(dp[n][ans])
print(ans);
printf("\n");
}
return 0;
}