Ural 1102 1112 1119 1138 1146
This post is written in Chinese. Please consider using Google Translate
==1102== 对于读入的每一行分别进行动态规划。
状态 F[i]前i为是否可以连续达到
状态转移方程 F[i]= or { F[i-Len[j] | i-Len[j]>=0 并且 S[i-Len[j]+1] 匹配 W[j] }
边界条件 F[0]=true
目标结果 F[L]
==1112==
我们先对所有的区间的左端进行排序，然后进行动态规划。设第0个区间坐标为(-1000,-1000)，第N+1个区间坐标为(1000,1000)。动态规划中记录下每个状态的前驱状态，用来输出方案。
状态 F[i] 前i的区间中，如果互不相交，留下的最大数量
状态转移方程
F[i] = Max{ F[j]+1 | j右端<=i左端 }
边界条件 F[0]=0
目标结果
F[N+1]-1
==1119==
这道题有明显的动态规划策略。首先不要按照方格来考虑，考虑顶点，这样目标点就是(N+1,M+1)。
---------算法1----------- 最直观的想法是按照矩阵动态规划。
设状态F[i,j]为走到点(i,j)时的最短路径
状态转移方程 F[i,j]=Min { F[i-1,j]+100 F[i,j-1]+100 F[i-1,j-1]+141.4213562373 }
边界条件 F[0,0]=0
F[N+1,M+1]就是结果。
但是对于8M的内存限制，要使用滚动数组。
时间复杂度为O(N*M)
---------算法2----------- 可以发现，如果我们只走直边的话，要走(N+M)100长度。如果走C条斜边，那么要走(C141.4213562373)+(N+M-C2)100 的长度。那么显然我们要尽可能使C更大，即多走斜边。
这样可以转化为经典的LIS模型。即把所有的斜边按照坐标排序，然后求最长的上升序列(x，y都要严格递增)，走这样的斜边一定是最优的策略。于是我们可以求出C。
结果就是(C141.4213562373)+(N+M-C2)*100。
Vijos 1336其实就是这道题的数据加大版。对于较小的K和很大的N,M，只能用算法2解决。
==1138==
看似简单，很容易出错的动态规划。我用了正向递推的方法。注意每次最大增量为100%，最后的结果不是到n的最大次数，而是小于等于n的最大次数。
设状态 F[i] 为薪水达i时，从最初的薪水到i时最大数目。F[i]为0时代表无法到达。
状态转移方程 F[j]=Max{ F[j],F[i]+1 } i=s..n-1 且F[i]不为0 k=1..100 表示增量 如果ik整除100，则j=i+ik/100。
边界条件 F[s]=1
目标结果 Max{ F[i] | i=s..n }
==1146==
最大子矩阵问题。对于这个问题，首先要把它转化成最大连续序列和问题然后再进行动态规划。思路为把矩阵“压缩”成一个序列。
对于矩阵，首先对每一行扫描，求出每行上任意一段序列和，时间复杂度为O(N^2)然后枚举每个段，对每行的这个段进行动态规划。
例如下列矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 当我们枚举到每行[1,2]，可以“压缩”为 -2 11 -3 7 对这个序列求最大连续序列和，即可求出当前位置边长的最大子矩阵。时间复杂度为O(N)，分别枚举每个段，时间复杂度为O(N^2)，总时间复杂度为O(N^3)。
动态规划状态设定 F[i,j]为矩阵第i行，前j项和。则可知第k行从i到j项和可表示为F[k,j]-F[j,i-1]。 G[i,j,k]为对于从i到j项的一段，以第k行为尾的前k行的每行项的最大和。
状态转移方程 F[i,j]=F[i,j-1] + Number[i,j] G[i,j,k]=Max{ G[i,j,k-1] + F[k,j]-F[j,i-1] , F[k,j]-F[j,i-1] }
目标解为 Max { G[i,j,k] }
以下是代码 ==1102==
#include <iostream>
#define MAX 4000001
using namespace std;
int N,L;
char S[MAX];
bool F[MAX];
char W[6][10]={"one","puton","out","in","input","output"};
int Len[6];
void init()
{
int i;
freopen("1102.in","r",stdin);
freopen("1102.out","w",stdout);
scanf("%d\n",&N);
for (i=0;i<6;i++)
Len[i]=strlen(W[i]);
}
bool match(char *S,char *k)
{
for (;*k;k++,S++)
if (*k!=*S)
return false;
return true;
}
bool dynamic()
{
int i,j;
F[0]=true;
for (i=1;i<=L;i++)
{
F[i]=false;
for (j=0;j<6;j++)
{
if (i-Len[j]>=0 && match(&S[i-Len[j]+1],W[j]))
{
if (F[i-Len[j]])
{
F[i]=true;
break;
}
}
}
}
return F[L];
}
int main()
{
init();
for (int i=1;i<=N;i++)
{
scanf("%s",S+1);
L=strlen(S+1);
memset(F,0,sizeof(F));
bool yes=dynamic();
if (yes)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
==1112==
#include <iostream>
#define MAX 100
using namespace std;
struct interval
{
int left,right;
};
int N,Ans;
interval S[MAX];
int F[MAX],G[MAX],A[MAX];
template <class T> void SWAP(T &a,T &b)
{
T c=a;a=b;b=c;
}
int cmp(const void *a,const void *b)
{
if (((interval *)a)->left< ((interval *)b)->left)
return -1;
if (((interval *)a)->right< ((interval *)b)->right)
return -1;
return 1;
}
void init()
{
int i;
freopen("1112.in","r",stdin);
freopen("1112.out","w",stdout);
cin >> N;
for (i=1;i<=N;i++)
{
cin >> S[i].left >> S[i].right;
if (S[i].left > S[i].right)
SWAP(S[i].left,S[i].right);
}
qsort(S+1,N,sizeof(S[0]),cmp);
}
void dynamic()
{
int i,j;
S[0].left=S[0].right=-1000;
S[N+1].left=S[N+1].right=1000;
for (i=1;i<=N+1;i++)
{
for (j=0;j<i;j++)
{
if (S[i].left>=S[j].right && F[j]+1>F[i])
{
F[i]=F[j]+1;
G[i]=j;
}
}
}
Ans=F[N+1]-1;
cout << Ans << endl;
for (i=G[N+1];i;i=G[i],Ans--)
A[Ans]=i;
for (i=1;i<=F[N+1]-1;i++)
cout << S[A[i]].left << ' ' << S[A[i]].right << endl;
}
int main()
{
init();
dynamic();
return 0;
}
==1119==
===算法一===
#include <iostream>
using namespace std;
const int MAX=1002;
const double Dc=141.42135623730950488016887242097;
const double Dl=100.0;
const double INF=1e20;
int M,N,P;
bool cross[MAX][MAX];
double F[2][MAX];
void init()
{
int i,a,b;
freopen("1119.in","r",stdin);
freopen("1119.out","w",stdout);
cin >> M >> N >> P;
N++;M++;
for (i=1;i<=P;i++)
{
cin >> b >> a;
a++;b++;
cross[a][b]=true;
}
cross[1][1]=true;
F[0][0]=-Dc;
}
void dynamic()
{
int i,j,p;
double min;
for (i=p=1;i<=N;i++,p=!p)
{
for (j=1;j<=M;j++)
{
min=INF;
if (i>1 && F[!p][j] + Dl <min)
{
min=F[!p][j] + Dl;
}
if (j>1 && F[p][j-1] + Dl <min)
{
min=F[p][j-1] + Dl;
}
if (cross[i][j] && F[!p][j-1] + Dc < min)
{
min=F[!p][j-1] + Dc;
}
F[p][j]=min;
}
}
printf("%.0lf",F[!p][M]);
}
int main()
{
init();
dynamic();
return 0;
}
===算法二===
#include <iostream>
using namespace std;
const int MAX=1002;
const double Dc=141.42135623730950488016887242097;
const double Dl=100.0;
const double INF=1e20;
struct Point
{
int x,y;
};
int M,N,P;
Point T[MAX];
int F[MAX];
double Ans;
inline int cmp(const void *a,const void *b)
{
if (((Point *)a)->x==((Point *)b)->x && ((Point *)a)->y<((Point *)b)->y)
return -1;
return ((Point *)a)->x < ((Point *)b)->x ?-1 :1;
}
void init()
{
int i,a,b;
freopen("1119.in","r",stdin);
freopen("1119.out","w",stdout);
cin >> M >> N >> P;
N++;M++;
for (i=1;i<=P;i++)
{
cin >> b >> a;
a++;b++;
T[i].x=a;
T[i].y=b;
}
qsort(T+1,P,sizeof(T[0]),cmp);
}
void dynamic()
{
int i,j,max,cnt=0,d;
for (i=1;i<=P;i++)
{
max=0;
for (j=0;j<=i-1;j++)
{
if (T[j].x<T[i].x && T[j].y<T[i].y && F[j] + 1 > max)
max=F[j]+1;
}
F[i]=max;
if (F[i]>cnt)
cnt=F[i];
}
d=N+M-cnt*2-2;
Ans=d*Dl + cnt*Dc;
printf("%.0lf",Ans);
}
int main()
{
init();
dynamic();
return 0;
}
==1138==
#include <iostream>
using namespace std;
const int MAX=10001;
int A,B,Ans;
int F[MAX];
void init()
{
freopen("1138.in","r",stdin);
freopen("1138.out","w",stdout);
cin >> B >> A;
}
void dynamic()
{
int i,j,k;
Ans=F[A]=1;
for (i=A;i<=B-1;i++)
{
if (!F[i]) continue;
for (k=1;k<=100;k++)
if (i*k%100==0)
{
j=i+i*k/100;
if (j>B) continue;
if (F[i]+1>F[j])
F[j]=F[i]+1;
if (F[j]>Ans)
Ans=F[j];
}
}
}
int main()
{
init();
dynamic();
cout << Ans;
return 0;
}
==1146==
#include <iostream>
using namespace std;
const int MAX=101;
const int INF=0x7FFFFFFF;
int Num[MAX][MAX],F[MAX][MAX];
int G[MAX];
int N,Ans=-INF;
void init()
{
int i,j;
freopen("1146.in","r",stdin);
freopen("1146.out","w",stdout);
cin >> N;
for (i=1;i<=N;i++)
{
for (j=1;j<=N;j++)
{
scanf("%d",&Num[i][j]);
}
}
}
void dynamic()
{
int i,j,k,Item;
for (i=1;i<=N;i++)
{
for (j=1;j<=N;j++)
{
F[i][j]=F[i][j-1]+Num[i][j];
}
}
for (i=1;i<=N;i++)
{
for (j=i;j<=N;j++)
{
for (k=1;k<=N;k++)
{
Item=F[k][j]-F[k][i-1];
if (G[k-1] + Item > Item)
G[k]=G[k-1] + Item ;
else
G[k]=Item;
if (G[k]>Ans)
Ans=G[k];
}
}
}
}
int main()
{
init();
dynamic();
cout << Ans ;
return 0;
}