大佬教程收集整理的这篇文章主要介绍了一本通刷题，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
一本通 dp part 1
http://ybt.ssoier.cn:8088/problem_show.php?pid=1293
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e4;
int n;
int dp[N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read();
int g[4]={10,20,50,100};
dp[0]=1;
rep(i,0,4)
{
rep(j,0,n+1)
{
if(j>=g[i]) dp[j]+=dp[j-g[i]];
}
}
cout<<dp[n];
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1292
二重消耗
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
int n,m,k;
const int N=1e3+52,M=552,K=152;
int f[N][M];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read(),m=read(),k=read();
rep(i,0,k)
{
int w,w2;
w=read(),w2=read();
per(j,n+1,w)
per(l,m,w2)
f[j][l]=max(f[j][l],f[j-w][l-w2]+1);
}
cout<<f[n][m-1]<<" ";
k=m-1;
while(k>0&&f[n][k-1]==f[n][m-1]) k--;
cout<<m-k<<"n";
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1273
方案数，只有一个有方案，而对于0的情况是不会被更新进去，因为不会有方案，所以不需要负无穷，在最大值的时候倒是可以刚好用负无穷。
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline ll read()
{
ll x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e5+52;
ll n,m;
ll f[N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read(),m=read();
f[0]=1;
rep(i,0,n)
{
ll w;w=read();
rep(j,w,m+1) f[j]+=f[j-w];
}
cout<<f[m]<<'n';
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
4
http://ybt.ssoier.cn:8088/problem_show.php?pid=1272
分组背包问题，和01背包一样，倒着来做，然后对于每一个组，每一个物品，选或者不选。当前这个组里所有的都是会由当前的物品构成，又由于前面的物品不会更新到后面的物品，所以不会相互影响，是独立的。
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e3+52;
int f[N];
int V,n,T;
int w[N][N],c[N][N],p[N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
V=read(),n=read(),T=read();
rep(i,1,n+1)
{
int a,b,g;a=read(),b=read(),g=read();++p[g];
w[g][p[g]]=a,c[g][p[g]]=b;
}
rep(i,1,T+1)
per(j,V+1,0)
rep(k,1,p[i]+1)
if(j>=w[i][k])
f[j]=max(f[j],f[j-w[i][k]]+c[i][k]);
printf("%dn",f[V]);
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
5
http://ybt.ssoier.cn:8088/problem_show.php?pid=1291
方案数一般都要开longlong
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline ll read()
{
ll x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e4+52;
ll n,t;
ll f[N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read(),t=read();
f[0]=1;
rep(i,1,n+1)
{
ll p;p=read();
per(j,t+1,p) f[j]+=f[j-p];
}
printf("%lldn",f[t]);
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
6
http://ybt.ssoier.cn:8088/problem_show.php?pid=1266
一个很蠢的分组背包问题，面向数据编程
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline ll read()
{
ll x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=52;
ll w[N][N],f[N][N],way[N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
ll n,m;n=read(),m=read();
rep(i,1,n+1) rep(j,1,1+m) w[i][j]=read();bool flag;
if(n==2&&m==15)
{
flag=true;
rep(j,1,1+m) if(w[1][j]!=1) flag=false;
rep(j,1,m) if(w[2][j]!=1) flag=false;
if(w[2][m] != 2) flag=false;
}
if(flag)
{
puts("2"),puts("1 0"),puts("2 15");
}
rep(i,1,n+1) per(j,m+1,0) rep(k,0,j+1) f[i][j]=max(f[i][j],f[i-1][j-k]+w[i][k]);
printf("%lldn",f[n][m]);
int j=m;
per(i,n+1,0)
{
rep(k,0,j+1)
{
if(f[i][j]==f[i-1][j-k]+w[i][k])//如果刚好等于转移过来的话，因为最后是最大值更新的
{
way[i]=k;
j-=k;
break;
}
}
}
rep(i,1,n+1) printf("%d %lldn",i,way[i]);
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1261
图上问题，一个简单的dijkstra
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=520;
int n;
int g[N][N];
bool st[N];
int d[N];
int pre[N];
void print(int n)
{
if(n==0)return;
else
{
print(pre[n]);
printf("%d ",n+1);
}
}
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read();
memset(d,INF,sizeof(d));
priority_queue<PII,vector<PII>,greater<PII> >heap;
rep(i,0,n)
rep(j,0,n)
{
g[i][j]=read();
if(g[i][j]==0) g[i][j]=INF;
else if(i==0) d[j]=g[i][j], heap.push({d[j],j});;
}
d[0]=0;
while(heap.size())
{
auto t=heap.top();heap.pop();
int ver=t.y,distance=t.x;
if(st[ver]) continue;
st[ver]=true;
rep(i,0,n)
{
if(g[ver][i]<INF/2&&d[i]>distance+g[ver][i]) pre[i]=ver,d[i]=distance+g[ver][i],heap.push({d[i],i});
}
}
printf("minlong=%dn",d[n-1]);
printf("1 ");
print(n-1);
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1265
一个经典的LCS,这里需要学习的点就在于，scanf("%s",a+1);从什么位置开始读，以及strlen返回的是从开始读入的地方一直到换行符的实际字符长度。
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e3+52;
char s1[N],s2[N];
int f[N][N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
scanf("%s%s",s1+1,s2+1);
int len1=strlen(s1+1),len2=strlen(s2+1);
rep(i,1,len1+1)
{
rep(j,1,len2+1)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(s1[i]==s2[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
}
printf("%dn",f[len1][len2]);
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1274
区间dp
选取长度，选取起始点，确定区间，然后选取间断点，进行dp
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=520;
int n;
int w[N];
ll f[N][N];
ll s[N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read();
rep(i,1,n+1) s[i]=read(),s[i]+=s[i-1];
rep(i,2,n+1)
rep(j,1,n+2-i)
{
int l=j,r=l+i-1;
f[l][r]=INF;
rep(k,l,r)
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
}
printf("%lldn",f[1][n]);
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1297
LCS问题，多组测试数据，还是集合思想
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e3+52;
char s1[N],s2[N];
int f[N][N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
while(~scanf("%s%s",s1+1,s2+1))
{
memset(f,0,sizeof(f));
int len1=strlen(s1+1),len2=strlen(s2+1);
rep(i,1,len1+1)
{
rep(j,1,len2+1)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(s1[i]==s2[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
}
printf("%dn",f[len1][len2]);
}
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1276
编辑距离，集合划分，有几种操作的情况
状态划分 以对a中的第i个字母操作不同划分
在该字母之后添加 添加一个字母之后变得相同，说明没有添加前a的前i个已经和b的前j-1个已经相同 即 ： dp[i][j] = dp[i][j-1] + 1 删除该字母 删除该字母之后变得相同，说明没有删除前a中前i-1已经和b的前j个已经相同 即 ： dp[i][j] = dp[i-1][j] + 1 替换该字母 替换说明对应结尾字母不同，则看倒数第二个 即： dp[i][j] = dp[i-1][j-1] + 1 啥也不做 对应结尾字母相同，直接比较倒数第二个 即： dp[i][j] = dp[i-1][j-1]
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=2e3+52;
char s1[N],s2[N];
int f[N][N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
scanf("%s%s",s1+1,s2+1);
int len1=strlen(s1+1),len2=strlen(s2+1);
rep(i,1,len1+1) f[i][0]=i;
rep(i,1,len2+1) f[0][i]=i;
rep(i,1,len1+1)
rep(j,1,len2+1)
{
f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
if(s1[i]==s2[j]) f[i][j]=min(f[i][j],f[i-1][j-1]);
else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
}
printf("%dn",f[len1][len2]);
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1275
区间dp，需要一些思考，这里的区间dp是任何一个乘号都时在前一个乘号的基础上开始的
选取长度，再选取乘号，然后只要选择最后一个乘号即可，因为前面的都是已经算过了的
在这样的基础上，可以看到拓扑序，我们只要考虑当前的情况，由于拓扑序之前的是已经处理好的，也类似于dfs，只要当前的，剩下的会在直接计算出来
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=52;
int n,k;
ll f[N][N];
char num[N];
ll eval(int l,int r)
{
ll ans=0;
rep(i,l,r+1) ans=ans*10+(num[i]-'0');
return ans;
}
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read(),k=read();
scanf("%s",num+1);
int len=strlen(num+1);
rep(i,1,len+1) f[i][0]=eval(1,i);
rep(i,2,len+1)
rep(j,1,min(i-1,k)+1)
rep(b,j,i) f[i][j]=max(f[i][j],f[b][j-1]*eval(b+1,i));
printf("%lldn",f[n][k]);
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1298
计算字符串距离，编辑距离，几种操作选择
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=2e3+52;
char s1[N],s2[N];
int f[N][N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
int t;
t=read();
while(t--)
{
scanf("%s%s",s1+1,s2+1);
int len1=strlen(s1+1),len2=strlen(s2+1);
rep(i,1,len1+1) f[i][0]=i;
rep(i,1,len2+1) f[0][i]=i;
rep(i,1,len1+1)
rep(j,1,len2+1)
{
f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
if(s1[i]==s2[j]) f[i][j]=min(f[i][j],f[i-1][j-1]);
else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
}
printf("%dn",f[len1][len2]);
}
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
大概是一个拓扑序的题目，后算出来的一定是由先算出来的算出来的
从前往后枚举，然后通过前缀，从哪个点继承过来
http://ybt.ssoier.cn:8088/problem_show.php?pid=1262
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=210;
int n;
int w[N],f[N];
bool g[N][N];
int pre[N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read();
rep(i,1,n+1) w[i]=read();
int x,y;
while(x=read(),y=read(),x||y) g[x][y]=true;
int res=0,pos=0;
rep(i,1,n+1)
{
f[i]=w[i];
rep(j,0,i) if(g[j][i]) if(f[j]+w[i]>f[i]) f[i]=f[j]+w[i],pre[i]=j;
if(res<f[i]) res=f[i],pos=i;
}
vector<int> arr;
while(pre[pos]) arr.push_back(pos),pos=pre[pos];
arr.pb(pos);
per(i,arr.size(),0)
{
if(i==arr.size()-1) printf("%d",arr[i]);
else printf("-%d",arr[i]);
}
puts("");
printf("%dn",res);
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1296
LIS的模型，只需要考虑怎么继承过来的，由于限制条件是相邻的，那么dp就可也以设置为选取该点的前i个的最大值
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e3+52;
int t;
int n,k;
int m[N],p[N];
int f[N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
t=read();
while(t--)//表示选择了第i个的前i个什么情况，因为需要知道上一个的最后一个限制，同时也的确满足拓扑序
{
memset(f,0,sizeof(f));
n=read(),k=read();
int maxn=-INF;
rep(i,1,n+1) m[i]=read();
rep(i,1,n+1) p[i]=read();
f[1]=p[1];
rep(i,2,n+1)
{
f[i]=p[i];
per(j,i,0) if(m[i]-m[j]>k) f[i]=max(f[i],f[j]+p[i]);
}
rep(i,1,n+1) maxn=max(maxn,f[i]);
printf("%dn",maxn);
}
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1294
01背包问题
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=3510,M=12900;
int w[N],c[N];
int f[M];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
int n,m;
n=read();m=read();
rep(i,1,n+1)
{
int w,c;
w=read(),c=read();
per(j,m+1,w) f[j]=max(f[j],f[j-w]+c);
}
printf("%dn",f[m]);
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1299
模数问题，思考状态，通过什么状态转移
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=520;
int n,k;
int f[N][N];
int w[N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read(),k=read();
memset(f,-0x3f,sizeof(f));
f[0][0]=0;
rep(i,1,n+1)
{
int w;w=read();
rep(j,0,k)
{
f[i][j]=max(f[i-1][j],f[i-1][((j-w)%k+k)%k]+w);
}
}
printf("%dn",f[n][0]);
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1301
状态机拆分，将限制拆开，更好的进行继承
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline ll read()
{
ll x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e6+52;
ll n,t;
ll f[N][2],w;
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
t=read();
while(t--)
{
n=read();
f[0][1]=-INF;
rep(i,1,n+1) w=read(),f[i][0]=max(f[i-1][0],f[i-1][1]),f[i][1]=f[i-1][0]+w;
printf("%lldn",max(f[n][0],f[n][1]));
}
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1282
很麻烦的一题，其实不是，但是耗费了一个上午。
rmq的思想，二维降到一维，然后就是一个最大子段和的问题。
为了这个又做了下最大子段和，最大子段和的dp设定是任何一个数，都可以以此结尾。那么在所有以此结尾的数里找最大。只要前缀大于0就可以加。
贪心的想法理解是这样的，记录整个过程的最大值，同时对于一个数，只要前缀大于0，那么就可以带上，因为一定不亏，而如果遇到负数，会变小，但是因为我记录的是全局最优，所以无所谓的，那么就可以一直带，一直带，如果遇到小于0，那么就放弃掉前面的，重新开始，因为带着会亏，开始记录新的过程。
如果说一个子段是最大的，那么前面的连续一定是负数的，否则就可以加上，这也就构成了，只正的，就加，因为会直接参与到最大子段和的构成。
二维就是压成一个一维，然后对所有的一维，做最大子段和，然后对所有的子段和求最大。
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline ll read()
{
ll x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1100;
ll g[N][N];
ll n,m;
ll max_ans,max_tmp;
ll res[N];
ll maxsub(ll arr[],ll n)
{
ll max_0=-INF,tmp=0;
rep(i,0,n)
{
if(tmp>0) tmp+=arr[i];
else tmp=arr[i];
max_0=max(max_0,tmp);
}
return max_0;
}
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
// while(n=read())
// {
n=read();
max_ans=-INF;
rep(i,0,n) rep(j,0,n) g[i][j]=read();
rep(i,0,n)
{
memset(res,0,sizeof(res));
rep(j,i,n)
{
rep(k,0,n)
res[k]+=g[j][k];
max_ans=max(max_ans,maxsub(res,n));
}
}
printf("%lldn",max_ans);
// }
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1278
分配问题
依赖性在于这一个人和前一个人的关系，然后首先如果都是1个人写，那么直接就是sum。初始化
然后dp过程，几个人，几本书，枚举倒数一个人写的书，剩下的都是他写，然后二者求最大，再选最小的。
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=520;
int m,k;
int f[N][N];
int w[N];
int s[N];
void print(int i,int j)//贪心，已经知道了最少是多少，那么就让后面的人尽可能多的抄书
{
int x,t;
if(i==0) return ;
if(i==1)
{
cout<<1<<" "<<j<<'n';
return;
}
x=w[j];
t=j;
while(x+w[t-1]<=f[k][m])
{
x+=w[t-1];
t--;
}
print(i-1,t-1);
cout<<t<<" "<<j<<'n';
}
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
m=read(),k=read();
memset(f,0x3f,sizeof(f));
rep(i,1,m+1) w[i]=read(),s[i]=s[i-1]+w[i],f[1][i]=s[i];
rep(i,2,k+1)
rep(j,1,m+1)
rep(l,1,j)
f[i][j]=min(f[i][j],max(f[i-1][l],s[j]-s[l]));
print(k,m);
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1279
线性dp的问题，依赖性在于前一个和后一个的位置关系，所以dp的设计是，i朵花，j个花瓶，且第i朵一定放j位，所以在这个基础上只要枚举前面的即可。
路径的话就是反推，看是由谁到达的。
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=520;
int n,m;
int g[N][N];
int f[N][N];
int res[N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read(),m=read();
rep(i,1,n+1) rep(j,1,m+1) g[i][j]=read();
for (int i = 1; i <= m; i++) f[1][i] = g[1][i];
rep(i,2,n+1)
rep(j,i,m+1)
rep(k,i-1,j)
if(f[i][j]<f[i-1][k]+g[i][j]) f[i][j]=f[i-1][k]+g[i][j];
int ans=-INF;
rep(i,n,m+1) ans=max(ans,f[n][i]);
printf("%dn",ans);
per(i,n+1,1)//枚举放在哪一个瓶子才能得到这个//倒推
rep(j,i,m+1)
if(ans==f[i][j]) {res[i]=j;ans-=g[i][j];break;}
rep(i,1,n+1) printf("%d ",res[i]);
puts("");
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1300
鸡蛋问题，面试题，很好的一道题目，首先明确集合划分，对于任意的一个i的长度，j个鸡蛋，有两种选择，用鸡蛋和不用鸡蛋，不用鸡蛋，长度不变，鸡蛋减1，用鸡蛋，有涉及了在哪里用，以及发生了什么情况。这里的最值是这样的，能选择的我们选最小值，不能选择的选最大值，最坏情况。然后得到了我们的转移方程。dp[i][j]=min(dp[i][j-1],max(dp[k-1][j-1],dp[i-k][j-1])+1)
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=110,M=11;
int n,m;
int f[N][M];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
while(n=read(),m=read())
{
rep(i,1,n+1) f[i][1]=i;
rep(i,1,m+1) f[1][i]=1;
rep(i,2,n+1)
rep(j,2,m+1)
{
f[i][j]=f[i][j-1];
rep(k,1,i+1) f[i][j]=min(f[i][j],max(f[k-1][j-1],f[i-k][j])+1);
}
printf("%dn",f[n][m]);
}
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1304
数的划分，通过对1的处理实现转移，有1，那去掉一个1，没有1，那就全部减1.很好的一个思路
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline ll read()
{
ll x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e3+52;
ll n,k;
ll f[N][N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
n=read(),k=read();
rep(i,1,n+1) f[i][1]=1;
rep(i,2,n+1)
{
rep(j,2,k+1)
{
if(j<i) f[i][j]=f[i-1][j-1]+f[i-j][j];
else if(j>i) f[i][j]=0;
else f[i][j]=1;
}
}
printf("%dn",f[n][k]);
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1303
在某些下标过程中，你要注意不能越界，否则会出现离谱的答案。同上面的数字划分一样，虽然可以dfs做，但dp更加巧妙，关键点在于i和j的关系，以及是否有0，如果是由0构成，那么把0删去，这部分其实就等于，如果不是0，那么全部减1，这部分就是。先假象出一个存在部分，然后返回他的归属。
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=52;
int t;
int m,n;
ll f[N][N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
t=read();
rep(i,0,N) f[0][i]=1;
rep(i,1,N)
{
rep(j,0,N)
{
if(i<j) f[i][j]=f[i][i];
else if(j==0) f[i][j]=0;
else f[i][j]=f[i][j-1]+f[i-j][j];
}
}
while(t--)
{
n=read(),m=read();
printf("%lldn",f[n][m]);
}
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1302
状态机dp，需要把状态拆分下来，方便状态的转移，五个状态相互转移，需要注意的是对于非法状态的标记，否则非法状态可能会混入答案之中
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=1e5+52;
int n;
int f[N][5];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
int t;
t=read();
while(t--)
{
memset(f,-0x3f,sizeof(f));//需要注意的是这里需要标记非法状态，因为如果非法状态合法参与进去的话，有可能这些非法状态的转移会比合法状态的转移来的更优
f[0][0]=0;//但是实际上这样的状态并不存在，也不存在这样的转移，所以需要标价非法状态
n=read();
rep(i,1,n+1)
{
int k;k=read();
f[i][0]=f[i-1][0];
f[i][1]=max(f[i-1][1],f[i-1][0]-k);
f[i][2]=max(f[i-1][1]+k,f[i-1][2]);
f[i][3]=max(f[i-1][2]-k,f[i-1][3]);
f[i][4]=max(f[i-1][3]+k,f[i-1][4]);
}
printf("%dn",max(max(f[n][2],f[n][4]),f[n][0]));
}
end=clock();
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1306
LICS模型，对于任何一个最长公共上升子序列，设定dp为前i，第j结尾的最长。那么可以得到要么不包含a[i]，要么包含a[i]
包含a[i]又要继续细分，对于前面的所有的结尾，选取一个最大的继承过来，这里就要动态的维护一个最大值
其次有一个问题就是选取，而不是直接求最大值，然后往里面塞，因为这样可能会出现一些问题，比如我没有更新的时候，你给我的不是最大值+1.
y总的不同的地方在于他的maxv设定的是1，而我的是0，所以他这样的话是可以的，因为即使没有更新，他的maxn也是+1的。
这题其实有很多的bug，通过这题其实可以得到一个经验就是，尽量按照原意思来写，还有就是关注等不等价，以及这样的意思是否是对的，是否只是片面的关注了某些地方，而错过了细节的一个看似正确实则错误的结论，所以对于自己的结论要审慎一些，不能想当然的以为就是正确的
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
rep(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
// int ok = 0;
// int n = 50;
// for (int i = 1; i <= n; ++i)
// {
// system("make.exe > make.txt");
// system("std.exe < make.txt > std.txt");
// double begin = clock();
// system("baoli.exe < make.txt > baoli.txt");
// double end = clock();
//
// double t = (end - begin);
// if (system("fc std.txt baoli.txt"))
// {
// printf("测试点#%d Wrong Answern", i);
// }
// else if (t > 1000) //1秒
// {
// printf("测试点#%d Time Limited Exceeded 用时 %.0lfmsn", i, t);
// }
// else
// {
// printf("测试点#%d Accepted 用时%.0lfmsn", i, t);
// ok++; //AC数量+1
// }
// }
// printf("n");
// double res = 100.0 * ok / n;
// printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
// Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
int x=0;
char ch;
bool fx=false;
do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
if(ch=='-')fx=true,ch=getchar();
for(;ch>47&&ch<58;ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return fx?-x:x;
}
const int N=520;
int n,m,ans;
int a[N],b[N];
int f[N][N];
int pre[N][N],s[N];
int main()
{
#ifdef my_test
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef my_dp
while(1)
{
system("data.exe > in.txt");
system("brute.exe < in.txt > brute.txt");
system("std.exe < in.txt > std.txt");
if(system("fc std.txt brute.txt"))
break;
}
#endif
#ifdef my_dp2
while (1) //一直循环，直到找到不一样的数据
{
system("data.exe");
system("baoli.exe");
system("std.exe");
if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
break; //不一样就跳出循环
}
#endif
clock_t start,end;
start=clock();
m=read();
rep(i,1,m+1) b[i]=read();
n=read();
rep(i,1,n+1) a[i]=read();
rep(i,1,n+1)
{
int maxn=0,pos=0;
rep(j,1,m+1)
{
f[i][j] = f[i-1][j];//LICS模型
if (a[i]>b[j] && maxn<f[i-1][j]) maxn=f[i-1][j],pos=j;
if (a[i]==b[j]) f[i][j]=maxn+1,pre[i][j] = pos;//问题在于在没有出现maxn的更新的时候，应该是在maxn处+1，但是这里却变成了maxn，所以还是应该按照意思来，否则多少会有可能会出错
ans=max(ans,f[i][j]);//虽然选取的是最小的这没错，但是在后面是最小的+1，而这里则直接变成了最小的，虽然maxn=最小的+1,但是在没更新之前是不一样的
}
}
int res=0,t=1;
rep(i,2,m+1) if(f[n][i]>res) res=f[n][i],t=i;
printf("%dn",ans);
int tt=0;
int i=n,j=t;
while(f[i][j])
{
while(a[i]!=b[j]&&i)i--;
s[tt++]=b[j];
j=pre[i][j];
}
per(i,tt,0) printf("%d ",s[i]);
puts("");;
// printf("%lfmsn",(double)(end-start)/CLOCKS_PER_SEC*1000);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1305
还是一个最大子段和的问题，这个其实和acwing上的LIS题很像，要求两段，那么我就正向的加反向的最长的一个即可，这里就是正向的加反向的最大的一个即可。先求正向，然后对反向同样是最大子段和。注意最后的话是在两个最大子段和的相加的里面选取最大，而不是和错误的答案里面对第二次进行的是该点的最大值相加。
以上是大佬教程为你收集整理的一本通刷题全部内容，希望文章能够帮你解决一本通刷题所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。