acm竞赛使用哪种语言比较好
为什么程序在acm上通不过？
为什么程序在acm上通不过？
在 OJ 系统上做题，要求是非常严格的，你得仔细看题目的要求。
首先，你得保证你编程的正确性，运行结果是否正确。
其次，有的题目要求性能，就是要求时间复杂度不能超过多少！
一个题目可能有多重解题思路，但是性能不行，也是不行的。
然后，可能有语言要求，你使用的语言不对！
总之，一定要看清楚题目要求！
Lis算法如何用C语言实现？
最长上升子序列问题是各类信息学竞赛中的常见题型，也常常用来做介绍动态规划算法的引例，笔者接下来将会对POJ上出现过的这类题目做一个总结，并介绍解决LIS问题的两个常用算法(n^2)和(nlogn).
问题描述:给出一个序列a1,a2,a3,a4,a5,a6,,求它的一个子序列（设为s1,s2,），使得这个子序列满足这样的性质，并且这个子序列的长度最长。输出这个最长的长度。（为了简化该类问题，我们将诸如最长下降子序列及最长不上升子序列等问题都看成同一个问题，其实仔细思考就会发现，这其实只是lt符号定义上的问题，并不影响问题的实质）
例如有一个序列:1 7 3 5 9 4 8,它的最长上升子序列就是 1 3 4 8 长度为4.
算法1(n^2):我们依次遍历整个序列，每一次求出从第一个数到当前这个数的最长上升子序列，直至遍历到最后一个数字为止，然后再取dp数组里最大的那个即为整个序列的最长上升子序列。我们用dp[i]来存放序列1-i的最长上升子序列的长度，那么dp[i]max(dp[j]) 1,(j∈[1, i-1]) 显然dp[1]1,我们从i2开始遍历后面的元素即可。
下面是模板：
//最长上升子序列(n^2)模板
//入口参数：1.数组名称 2.数组长度（注意从1号位置开始）
templateltclass Tgt
int LIS(T a[],int n)
{
int i,j
int ans1
int m0
int *dpnew int[n 1]
dp[1]1
for(i2iltni )
{
m0
for(j1jltij )
{
if(dp[j]gtmampampa[j]lta[i])
mdp[j]
}
dp[i]m 1
if(dp[i]gtans)
ansdp[i]
}
return ans
}
算法2(nlogn):维护一个一维数组c，并且这个数组是动态扩展的，初始大小为1，c[i]表示最长上升子序列长度是i的所有子串中末尾最小的那个数，根据这个数字，我们可以比较知道，只要当前考察的这个数比c[i]大，那么当前这个数一定能通过c[i]构成一个长度为i 1的上升子序列。当然我们希望在C数组中找一个尽量靠后的数字，这样我们得到的上升子串的长度最长，查找的时候使用二分搜索，这样时间复杂度便下降了。 模板如下：
//最长上升子序列nlogn模板
//入口参数:数组名 数组长度，类型不限，结构体类型可以通过重载运算符实现
//数组下标从1号开始。
/**//////////////////////////BEGIN_TEMPLATE_BY_ABILITYTAO_ACM////////////////////////////
templateltclass Tgt
int bsearch(T c[],int n,T a)
{
int l1, rn
while(lltr)
{
int mid (l r)/2
if( a gt c[mid] ampamp a lt c[mid 1] ) return mid 1 // gtampamplt 换为: gt ampamp lt
else if( a lt c[mid] ) r mid-1
else l mid 1
}
}
templateltclass Tgt
int LIS(T a[], int n)
{
int i, j, size 1
T *cnew T[n 1]
int *dpnew int[n 1]
c[1] a[1] dp[1] 1
for(i2iltn i)
{
if( a[i] lt c[1] ) j 1// lt 换为: lt
else if( a[i] gtc[size] )
j size // gt 换为: gt
else
j bsearch(c, size, a[i])
c[j] a[i] dp[i] j
}
return size
}