今天练了一波DP。时间紧迫我就只贴代码了。
20141120
fzu2129
http://acm.fzu.edu.cn/problem.php?pid=2129
不同的子序列个数
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define mz(array) memset(array, 0, sizeof(array))
#define mf1(array) memset(array, -1, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("brackets.in","r",stdin)
#define WE freopen("brackets.out","w",stdout)
#define mp make_pair
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
typedef long long ll;
typedef unsigned long long ull; const double pi=acos(-1.0);
const double eps=1e-; const ll MOD=1e9+;
ll MMOD = MOD*;
const int maxn=; int a[maxn];
int n; ll f[maxn];
int d[maxn]; ll farm() {
int i;
mf1(d);
mz(f);
f[]=;
FOR(i,,n) {
if(d[a[i]]==-) f[i]=(f[i-] + f[i-]+)%MOD;
else{
f[i]=f[i-] + f[i-] - f[d[a[i]]-];
f[i]+=MMOD;
f[i]%=MOD;
}
d[a[i]]=i;
}
return f[n];
} int main() {
//RE;
//WE;
int i;
while(RD(n)!=EOF) {
FOR(i,,n)RD(a[i]);
printf("%I64d\n",farm());
}
}
ASC17 A题
http://codeforces.com/gym/100221
不同的括号子序列个数，要用java的BigInteger。
import java.util.*;
import java.io.*;
import java.math.BigInteger; public class Main {
public static final int MAXN = 333;
public static char[] s = null;
public static int N;
public static BigInteger[][] f = new BigInteger[MAXN][MAXN];
public static final BigInteger F1 = BigInteger.valueOf(-1);
public static final BigInteger ZERO = BigInteger.valueOf(0);
public static final BigInteger ONE = BigInteger.valueOf(1); public static BigInteger gank(int last, int o) {
// System.out.printf("Gank %d,%d\n",last,o);
if (last >= 0 && !f[last][o].equals(F1))
return f[last][o];
BigInteger re = ZERO;
if (o == 0)
re = ONE;
int i = last + 1;
while (i < N && (s[i] != '('))
i++;
if (i < N)
re = re.add(gank(i, o + 1));
if (o > 0) {
i = last + 1;
while (i < N && (s[i] != ')'))
i++;
if (i < N)
re = re.add(gank(i, o - 1));
}
if (last >= 0)
f[last][o] = re;
return re;
} public static void main(String[] args) throws Exception {
File fin = new File("brackets.in");
File fout = new File("brackets.out");
InputStream ins = new FileInputStream(fin);
OutputStream ous = new FileOutputStream(fout);
Reader.init(ins);
String S = Reader.next();
s = S.toCharArray();
N = S.length();
for (int i = 0; i < MAXN; i++) {
for (int j = 0; j < MAXN; j++) {
f[i][j] = F1;
}
}
BigInteger ans = gank(-1, 0);
ous.write(ans.toString().getBytes());
}
} class Reader {
static BufferedReader reader;
static StringTokenizer tokenizer; /** call this method to initialize reader for InputStream */
static void init(InputStream input) {
reader = new BufferedReader(new InputStreamReader(input));
tokenizer = new StringTokenizer("");
} /** get next word */
static String next() throws IOException {
while (!tokenizer.hasMoreTokens()) {
// TODO add check for eof if necessary
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
} static int nextInt() throws IOException {
return Integer.parseInt(next());
} static double nextDouble() throws IOException {
return Double.parseDouble(next());
}
}
Knapsack
带路径输出的背包，感觉直接用二维数组会好一点，这个有点乱。
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cassert>
using namespace std;
#define mz(array) memset(array, 0, sizeof(array))
#define mf1(array) memset(array, -1, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define FORD(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("knapsack.in","r",stdin)
#define WE freopen("knapsack.out","w",stdout)
#define mp make_pair
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double LD; const int maxm=;
const int maxn=; int dp[maxm], c[maxm], n, m, w[maxn], v[maxn];
int d[maxn][maxm];
vector<int> V;
int main() {
RE;
WE;
// freopen("in.txt","r",stdin);
while(~scanf("%d%d", &n, &m)) {
memset(dp, ,sizeof(dp));
memset(c, -, sizeof(c));
mz(d);
assert(n>&&n<=);
assert(m>&&m<=);
for(int i=; i<=n; i++) scanf("%d", &v[i]);
for(int i=; i<=n; i++) scanf("%d", &w[i]);
for(int i=;i<=n;i++){
assert(v[i]>=&&v[i]<=);
assert(w[i]>=&&w[i]<=);
//while(1);
//return 0; }
for(int i=; i<=n; i++) {
for(int j=m; j>=v[i]; j--) {
assert(j>=v[i]);
if(dp[j] < dp[j - v[i]] + w[i]) {
dp[j] = dp[j - v[i]] + w[i];
c[j] = i;
d[i][j]=c[j-v[i]];
}
}
}
int tmp=, mx = ;
for(int i=m; i>; i--)
if(dp[i] > mx) {
mx = dp[i];
tmp = i;
}
V.clear();
if(tmp==){
puts("");
continue;
}
V.pb(c[tmp]);
int i=d[c[tmp]][tmp]; tmp-=v[c[tmp]];
while(i > && tmp>=) {
V.pb(i);
int t=v[i];
assert(tmp>=&&tmp<=m);
i=d[i][tmp];
tmp -= t;
}
int sz = V.size();
printf("%d\n",sz);
sort(V.begin(),V.end());
for(int i=;i<sz;i++){
printf("%d%c",V[i],i==sz-?'\n':' ');
}
//if(sz==0)puts("");
}
return ;
}
Dominoes
15*100的1*2铺砖
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<climits>
using namespace std;
#define mz(array) memset(array, 0, sizeof(array))
#define mf1(array) memset(array, -1, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define FORD(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("dominoes.in","r",stdin)
#define WE freopen("dominoes.out","w",stdout)
#define mp make_pair
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double LD;
const ll MOD=1e9;
int m,n; const int maxs=(<<)+;
const int maxn=;
int f[maxn][maxs]; inline void dfs(const int &H, const int &s,const int &ss,const int &d){
if(d==m){
f[H][ss] += f[H-][s];
f[H][ss] %= MOD;
return;
}
if(s&(<<d))dfs(H,s,ss,d+);
else{
dfs(H,s, ss|(<<d) ,d+);
if(d<m- && ((s&(<<(d+)))==))
dfs(H, s, ss, d+);
}
} inline int farm(){
int i,j,k;
int maxi=<<m;
mz(f);
f[][]=;
FOR(i,,n){
REP(j,maxi)
if(f[i-][j]){
dfs(i,j,,);
}
}
return f[n][];
} int main(){
RE;
WE;
while(RD2(m,n)!=EOF){
printf("%d\n",farm());
}
return ;
}
Number of paths in acyclic graph
有向无环图判1~n的路径数。
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define mz(array) memset(array, 0, sizeof(array))
#define mf1(array) memset(array, -1, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define FORD(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("countpaths.in","r",stdin)
#define WE freopen("countpaths.out","w",stdout)
#define mp make_pair
#define pb push_back
#define pf push_front
#define ppf pop_front
#define maxn 100005
#define maxm 200005 int head[maxn];
int en;
#define ll long long
struct pp{
int v,next; }e[maxm];
void add(int u,int v){
e[en].v=v;
e[en].next=head[u];
head[u]=en++;
} ll f[maxn];
#define mod 1000000007 ll dfs(ll x){
if(f[x]!=-)return f[x];
ll re=;
int i;
for(i=head[x]; i!=-; i=e[i].next){
re+=dfs(e[i].v);
re%=mod;
}
f[x]=re;
return re;
} int main(){
int n,m;
RE;
WE;
scanf("%d%d",&n,&m);
memset(head,-,sizeof(head));
en=;
for(int i=;i<m;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
memset(f,-,sizeof(f));
f[n]=;
cout<<dfs()<<endl;
}
Longest common subsequence
LCS带路径输出
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define mz(array) memset(array, 0, sizeof(array))
#define mf1(array) memset(array, -1, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define FORD(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("lcs.in","r",stdin)
#define WE freopen("lcs.out","w",stdout)
#define mp make_pair
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double LD; const int maxn=; int n,m;
int a[maxn];
int b[maxn]; int f[maxn][maxn];
pair<int,int> pre[maxn][maxn]; int ans;
vector<int>an; void farm() {
int i,j;
mz(f);
FOR(i,,n) {
FOR(j,,m) {
if(a[i]==b[j]) {
f[i][j]=f[i-][j-] + ;
pre[i][j]=mp(i-,j-);
} else {
if(f[i-][j]>f[i][j-])f[i][j]=f[i-][j] , pre[i][j]=mp(i-,j);
else f[i][j]=f[i][j-] , pre[i][j]=mp(i,j-);
}
}
}
ans=f[n][m];
i=n,j=m;
an.clear();
while(f[i][j]!=){
int qi=pre[i][j].first;
int qj=pre[i][j].second;
if(f[i][j]>f[qi][qj])an.pb(a[i]);
i=qi,j=qj;
}
} int main() {
RE;
WE;
int i;
while(RD(n)!=EOF) {
FOR(i,,n)RD(a[i]);
RD(m);
FOR(i,,m)RD(b[i]);
farm();
printf("%d\n",ans);
if(ans>)printf("%d",an[ans-]);
FORD(i,ans-,){
printf(" %d",an[i]);
}
puts("");
}
return ;
}
Levenshtein distance
编辑距离？队友写的，日后我再看看。
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define mz(array) memset(array, 0, sizeof(array))
#define mf1(array) memset(array, -1, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define FORD(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("levenshtein.in","r",stdin)
#define WE freopen("levenshtein.out","w",stdout)
#define mp make_pair
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back //#define inf 0x7fffffff
//char a[5005],b[5005];
//int dp[5005][5005];
//int main(){
// while(scanf("%s%s",a,b)==2){
// int len1=strlen(a);
// int len2=strlen(b);
// for(int i=0;i<=len1;i++)
// for(int j=0;j<=len2;j++)dp[i][j]=inf;
// for(int i=0;i<=len1;i++)dp[0][i]=i;
// for(int i=0;i<=len2;i++)dp[i][0]=i;
// for(int i=1;i<=len1;i++){
// for(int j=1;j<=len2;j++){
// dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+(b[i]==a[j])?0:1));
// }
// }
// cout<<dp[len1][len2]<<endl;
// }
// return 0;
//}
// char s1[],s2[];
int d[][];
int min(int a,int b,int c) {
int t = a < b ? a : b;
return t < c ? t : c;
}
void editDistance(int len1,int len2)
{
int i,j;
for(i = ;i <= len1;i++)
d[i][] = i;
for(j = ;j <= len2;j++)
d[][j] = j;
for(i = ;i <= len1;i++)
for(j = ;j <= len2;j++)
{
int cost = s1[i-] == s2[j-] ? : ;
int deletion = d[i-][j] + ;
int insertion = d[i][j-] + ;
int substitution = d[i-][j-] + cost;
d[i][j] = min(deletion,insertion,substitution);
}
printf("%d\n",d[len1][len2]);
}
int main()
{
RE;
WE;
while(scanf("%s %s",s1,s2) != EOF)
editDistance(strlen(s1),strlen(s2));
return ;
}
Longest increasing subsequence
LIS，带路径输出
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define mz(array) memset(array, 0, sizeof(array))
#define mf1(array) memset(array, -1, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define FORD(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("lis.in","r",stdin)
#define WE freopen("lis.out","w",stdout)
#define mp make_pair
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double LD; const int maxn=; int n;
int a[maxn]; int f[maxn];
int pre[maxn]; int ans;
vector<int>an; inline void farm() {
int i,j;
mz(pre);
FOR(i,,n) {
f[i]=;
FOR(j,,i-) {
if(a[i]>a[j] && f[j]+>f[i]) {
f[i]=f[j]+;
pre[i]=j;
}
}
}
ans=;
int ai=;
FOR(i,,n) {
if(f[i]>ans)ans=f[i], ai=i;
}
i=ai;
an.clear();
REP(j,ans) {
an.pb(a[i]);
i=pre[i];
}
} int main() {
RE;
WE;
int i;
while(RD(n)!=EOF) {
if(n>=maxn)while();
FOR(i,,n)RD(a[i]);
farm();
printf("%d\n",ans);
if(ans>)printf("%d",an[ans-]);
FORD(i,ans-,) {
printf(" %d",an[i]);
}
puts("");
}
return ;
}
Maximal weight matching in tree
树上选一些边，没有公共顶点，要求边权和最大。
树DP，队友写的。
哇，代码不见啦！反正就是f[i][j],j=0~1,0是不用这个点，1是用这个点。
Matrix multiplication
矩阵链乘，加括号使得代价最小，带路径输出。算法导论题，队友写的，碉
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<climits>
using namespace std;
#define mz(array) memset(array, 0, sizeof(array))
#define mf1(array) memset(array, -1, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define FORD(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("matrix.in","r",stdin)
#define WE freopen("matrix.out","w",stdout)
#define mp make_pair
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double LD; const int maxn= + ; int n, a[maxn], b[maxn], m[maxn][maxn], s[maxn][maxn];
void Print(int l ,int r){
if(l == r){
putchar('A');
return;
}
putchar('(');
Print(l, s[l][r]);
Print(s[l][r] + , r);
putchar(')');
}
int main(){
RE;
WE;
scanf("%d", &n);
for(int i=; i<=n; i++) scanf("%d%d", &a[i], &b[i]), m[i][i] = ;
for(int l=; l<=n; l++){
for(int i=; i<=n-l+; i++){
int j = i + l -;
m[i][j] = INT_MAX;
for(int k=i; k<j; k++){
int q = m[i][k] + m[k + ][j] + a[i] * b[k] * b[j];
if(q < m[i][j]){
m[i][j] = q;
s[i][j] = k;
}
}
}
}
// cout << m[1][n] << endl;
Print(, n);
return ;
}
Longest subpalindrome
最长回文子串，带路径输出。
f[l][r]记录区间[l,r]的最长回文子串长度，区间从小到大搞。
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<climits>
using namespace std;
#define mz(array) memset(array, 0, sizeof(array))
#define mf1(array) memset(array, -1, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define FORD(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("palindrome.in","r",stdin)
#define WE freopen("palindrome.out","w",stdout)
#define mp make_pair
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double LD; const int maxn=; char s[];
int f[][];
pair<int,int> pre[maxn][maxn]; int ans;
vector<char>anl,anr; void farm(){
int len=strlen(s);
int i,j,k;
mz(f);
mf1(pre);
REP(i,len)f[i][i]= , pre[i][i]=mp(-,-);
FOR(k,,len-){
FOR(i,,len-){
j=i+k;
if(j>len-)break;
if(s[i]==s[j]){
if(j-i>){
f[i][j]=f[i+][j-]+;
pre[i][j] = mp(i+,j-);
}else{
f[i][j]=;
pre[i][j]=mp(-,-);
}
}else{
if(f[i][j-] > f[i+][j])f[i][j]=f[i][j-] , pre[i][j]=mp(i,j-);
else f[i][j]=f[i+][j] , pre[i][j]=mp(i+,j);
}
}
}
ans=f[][len-];
i=;
j=len-;
anl.clear();
anr.clear();
int qi,qj;
while(i>= && j>=){
qi=pre[i][j].first;
qj=pre[i][j].second;
if(qi< || qj<){
if(f[i][j]!=){
if(i==j)anl.pb(s[i]);
else anl.pb(s[i]),anr.pb(s[i]);
}
break;
}
//printf("%d,%d %d,%d %d,%d\n",i,j,qi,qj,f[i][j] , f[qi][qj]);
if(f[i][j] > f[qi][qj]){
if(i!=j)anl.pb(s[i]), anr.pb(s[i]);
else anl.pb(s[i]);
//printf("%d,%c\n",i!=j,s[i]);
}
i=qi;
j=qj;
}
} int main(){
int i;
RE;
WE;
while(scanf("%s",s)!=EOF){
farm();
printf("%d\n",ans);
REP(i,anl.size())putchar(anl[i]);
FORD(i,anr.size()-,)putchar(anr[i]);
puts("");
}
}
Travelling salesman problem
旅行商问题，代码不见了。
f[i][j]，一个是状压的到过哪个地方的状态，另一个是最后在哪个点。
String Decomposition
把字符串弄成又几个子串增殖出来的
太难啦，还没做出来
Solid Tilings
另一种比较难的铺砖，还没看。